It's interesting that P=NP can be proved or disproved by a single example or counterexample in either direction. It can be disproved by finding a single counterexample of a problem that is NP but not P. By the magic of computability theory, it can also be proved by finding a single example of an NP-complete problem that can by solved in deterministic polynomial time.
I know of of no other hard, unsolved, problems that have this property. Usually the counterexample is ``easy'' but the proof is hard.
Furthermore, instead of explicitly finding an example or counterexample, one only needs to show existence. However, how frustrating will it be if someone proves the existence of an NP-complete problem solvable in poly-time without constructing an example?
No comments :
Post a Comment