Medical diagnosis and treatment is NP-complete
Medical diagnosis and treatment is NP-complete
复制标题
DOI：
10.1080/0952813x.2020.1737581
复制
发表时间：
2020-03-13
影响因子：
2.2
通讯作者：
Carlson, Kristen W.
中科院分区：
文献类型：
--
作者：
Arle, Jeffrey. E.;Carlson, Kristen W.
人们对追求以程序为驱动的、按算法分配保健资源，包括计算机辅助医疗诊断和治疗，有很大的兴趣。关于MDT的计算复杂性，人们知之甚少;然而，如果确定了复杂性，那么复杂性与MDT自动化的相关性如何。我们以几种方式分析MDT的计算复杂性：（1）证明MDT在计算上是难处理的（NP完全，NPC）通过减少旅行销售员（TSP）和集合覆盖（2）相反，示出了易于处理的形式的MDT的示例，以及（3）示出了，撇开TSP和SETCOVER，存在计算效率，基于人类诊断方法的医学驱动搜索方法。计算表明，在所有可能的集合的空间中，实际的重复治疗集合的稀疏性是天文数字（例如，10（-204，678））。虽然MDT的计算复杂性在理论上是有趣的，但实用地揭示MDT的实际人类认知实践将加速人工智能的发展，以帮助并最终取代医生。
There is great interest in the pursuit of process-driven, algorithmic allocation of health-care resources, including computer-aided medical diagnosis and treatment (MDT). Little is understood regarding the computational complexity of MDT; however, and if determined, how relevant the complexity would be to automating MDT. We approach analysing the computational complexity of MDT in several ways: (1) proving that MDT is computationally intractable (NP-complete, NPC) by reducing the travelling salesperson (TSP) and set-cover (SETCOVER) problems to MDT, (2) showing, in contrast, an example of MDT in tractable form, and (3) showing that, leaving aside TSP and SETCOVER, there are computationally efficient, heuristic-driven search methods based on human diagnostician methods. Calculations show that the sparseness of actual symptom-treatments sets in the space of all possible sets is astronomical (e.g., 10(-204,678)). While the computational complexity of MDT is interesting theoretically, pragmatically uncovering actual human cognitive practices of MDT will accelerate the development of artificial intelligence to assist and eventually replace physicians.