ALGORITHMIC COMPLEXITY AND PRACTICAL PROBLEMS

算法复杂性和实际问题

• 批准号: 5203635
• 负责人: W WILBUR
• 金额: --
• 依托单位: NATIONAL LIBRARY OF MEDICINE
• 依托单位国家: 美国
• 资助国家: 美国
• 起止时间: 至
• 项目状态: 未结题
• 来源: https://reporter.nih.gov/project-details/5203635
• 关键词: artificial intelligence; computer program /software; computer system design /evaluation

Algorithmic complexity, as developed by Gregory Chaitin, shows that there are theoretical limits on the computational ability of computers. One of its achievements is an algorithmic form of Godel's famous theorem on the incompleteness of formal systems. However, in the Chaitin theory there is no limitation put on resources. In an attempt to make an analysis of more practical problems where there are limitations on resources, we have modified the Chaitin definition of algorithmic information to incorporate a limit on resources. With this modification we are able to prove a modified form of Godel's theorem and establish certain bounds on computational complexity. In particular we can demonstrate the existence of certain intractable decision problems. Research is ongoing in this area.

格雷戈里·蔡廷（Gregory Chaitin）提出的数学复杂性表明， 是计算机计算能力的理论极限。 一 它的成就之一是哥德尔著名定理的算法形式， 正式系统的不完整性。 然而，在蔡廷理论中， 对资源没有限制。 为了分析更多的实际问题， 是资源的限制，我们修改了Chaitin的定义， 算法信息以结合对资源的限制。 与此 修改，我们能够证明哥德尔定理的修改形式， 在计算复杂度上建立一定的界限。 我们尤其 可以证明某些棘手的决策问题的存在。 这方面的研究正在进行中。