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.