Optimal proof systems imply complete sets for promise classes

摘要

A polynomial time computable function h : Sigma* --> Sigma* whose range is a set L is called a proof system for L. In this setting, an h-proof for x is an element of L is just a string omega with h(omega) = x. Cook and Reckhow defined this concept in [13], and in order to compare the relative strength of different proof systems for the set TAUT of tautologies in propositional logic, they considered the notion of p-simulation. Intuitively, a proof system h' p-simulates h if any h-proof w can be translated in polynomial time into an h'-proof omega' for h(omega). We also consider the related notion of simulation between proof systems where it is only required that for any h-proof w there exists an h'-proof w' whose size is polynomially bounded in the size of omega. A proof system is called (p-)optimal for a set L if it (p-)simulates every other proof system for L. The question whether p-optimal or optimal proof systems for TAUT exist is an important one in the field. In this paper we show a close connection between the existence of (p-)optimal proof systems and the existence of complete problems for certain promise complexity classes like UP, NP boolean AND Sparse, RP or BPP. For this we introduce the notion of a test set for a promise class C and prove that C has a many-one complete set if and only if C has a test set T with a p-optimal proof system. If in addition the machines defining a promise class have a certain ability to guess proofs, then the existence of a p-optimal proof system for T can be replaced by the presumably weaker assumption that T has an optimal proof system. Strengthening a result from Krajicek and Pudlak [20], we also give sufficient conditions for the existence of optimal and p-optimal proof systems. (C) 2003 Elsevier Science (USA). All rights reserved. [References: 28]