ECCC-Report TR08-107https://eccc.weizmann.ac.il/report/2008/107Comments and Revisions published for TR08-107en-usThu, 11 Dec 2008 19:20:06 +0200
Paper TR08-107
| Optimal Proof Systems and Complete Languages |
Zenon Sadowski
https://eccc.weizmann.ac.il/report/2008/107We 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.
Thu, 11 Dec 2008 19:20:06 +0200https://eccc.weizmann.ac.il/report/2008/107