language: en

The Relative Complexity of NP Search Problems

Paul Beame
Computer Science and Engineering University of Washington
beame@cs.washington.edu
Stephen Cook
Computer Science Dept. University of Toronto
sacook@cs.toronto.edu
Jeff Edmonds
I.C.S.I.
Berkeley, CA 94704-1198
edmonds@icsi.berkeley.edu
Russell Impagliazzo x
Computer Science and Engineering UC, San Diego
9500 Gilman Drive La Jolla, CA 92093-0114
russell@cs.ucsd.edu
Toniann Pitassi -
Mathematics and Computer Science University of Pittsburgh
toni@cs.pitt.edu

Abstract 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 computation-ally equivalent to any decision problem. (Naturally, absolute separations would imply that P 6= 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 Null-stellensatz over finite fields.

[Research supported by NSF grants CCR-8858799 and CCR-9303017 Research supported by an NSERC operating grant and the Information Technology Research Centre Supported by an NSF postdoctoral fellowship and by a Canadian NSERC postdoctoral fellowship x Research Supported by NSF YI Award CCR-92-570979, Sloan Research Fellowship BR-3311, grant #93025 of the joint US-Czechoslovak Science and Technology Program, and USA-Israel BSF Grant 92-00043 Research supported by an NSF postdoctoral fellowship and by NSF Grant CCR-9457782]

1 Introduction