Logical Approaches to Computational Barriers

Optimal proof systems and complete languages

Speaker:
| Zenon Sadowski |

Slot: |
Array, 11:40-12:00, col. 5 |

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 |