The Relative Complexity of NP Search Problems

✍ Scribed by Paul Beame; Stephen Cook; Jeff Edmonds; Russell Impagliazzo; Toniann Pitassi

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 521 KB
• Volume: 57
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1575

✦ Synopsis

Papadimitriou introduced several classes of NP search problems based on combinatorial principles which guarantee the existence of solutions to the problems. Many interesting search problems not known to be solvable in polynomial time are contained in these classes, and a number of them are complete problems. We consider the question of the relative complexity of these search problem classes. We prove several separations which show that in a generic relativized world the search classes are distinct and there is a standard search problem in each of them that is not computationally equivalent to any decision problem. (Naturally, absolute separations would imply that P{NP.) Our separation proofs have interesting combinatorial content and go to the heart of the combinatorial principles on which the classes are based. We derive one result via new lower bounds on the degrees of polynomials asserted to exist by Hilbert's nullstellensatz over finite fields.