ALGORITHMIC COMPLEXITY AND PRACTICAL PROBLEMS

点击翻译按钮获取中文摘要

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.