ALGORITHMIC COMPLEXITY AND PRACTICAL PROBLEMS

算法复杂性和实际问题

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

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.

算法复杂度，由格雷戈里·查廷提出，