Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Optimal proof systems and complete languages

Edit abstract data

Speaker: Zenon Sadowski
Slot: Thu, 11:40-12:00, Room 19 (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 Valid HTML 4.01! Valid CSS!