Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Optimal proof systems and complete languages


Speaker: Zenon Sadowski
Slot: Array, 11:40-12:00, col. 5

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

websites: Arnold Beckmann 2008-05-19