Self-witnessing polynomial-time complexi
โ
Michael R. Fellows; Neal Koblitz
๐
Article
๐
1992
๐
Springer
๐
English
โ 295 KB
Abstracl. For a number of computational search problems, the existence of a polynomial-time algorithm for the problem implies that a polynomial-time algorithm for the problem is constructively known. Some instances of such self-witnessing polynomial-lime complexity are presented. Our main resuk demo