Computational complexity theory: Difference between revisions

Revision as of 16:06, 9 December 2001

Revision as of 05:47, 14 December 2001

Line 37:

The set '''[[P]]''' is the set of decision problems that can be solved in [[Big O|polynomial time]]. The set '''[[NP]]''' is the set of decision problems whose

solution can be verified in [[Big O|polynomial time]]. The question of whether '''P''' is the same set as '''[[NP]]''' is the most important open question in all of theoretical computer science. There is even a $1,000,000 prize for solving it. (See [[Complexity classes P and NP]] and [[Oracle machine|oracles]]).