Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-107 | 12th November 2008 00:00

Optimal Proof Systems and Complete Languages

RSS-Feed




TR08-107
Authors: Zenon Sadowski
Publication: 11th December 2008 19:20
Downloads: 1591
Keywords: 


Abstract:

We investigate the connection between optimal propositional
proof systems and complete languages for promise classes.
We prove that an optimal propositional proof system exists
if and only if there exists a propositional proof system
in which every promise class with the test set in co-NP
is representable. Additionally, we prove that there exists
a complete language for UP if and only if there exists
a propositional proof system such that UP is representable
in it. UP is the standard promise class with the test set
in co-NP.



ISSN 1433-8092 | Imprint