http://www.umiacs.umd.edu/users/liberato/cats/

Lance Fortnow

NEC Research

Wednesday, September 29, 1999, 4 p.m.

AVW 2120

Computer scientists study lower bounds in proof complexity with the ultimate hope of actual complexity class separation. Cook and Reckhow formalize this approach. They create a general notion of a proof system and show that polynomial-size proof systems exist if and only if NP = coNP.

Cook and Reckhow also ask about the possibility of whether optimal proof systems exist. Informally an optimal proof system would have proofs which are no more than polynomially longer than any other proof system.

An optimal proof system would play a role similar to NP-complete sets. There exists a polynomial-time algorithm for Satisfiability if and only if P = NP. Likewise, if we have an optimal proof system, then this system would have polynomial-size proofs if and only if NP = coNP.

The existence of optimal proof systems remains an interesting open question. Krajicek and Pudlak and Messner and Toran show that optimal proof systems do occur under some (unlikely) assumptions.

Messner and Toran show that the existence of optimal proof systems implies that there is a complete set for the class of sparse NP sets. This means there would be a single "small" NP set that is hard for every other "small" set. However they could not argue that these complete sets could not exist.

We show that proving the existence of optimal proof systems will require new techniques by creating a relativized world where there do not exist complete sets for the class of sparse NP sets. We also prove other results along these lines as well as tying together the question of complete sparse NP sets and reductions from sparse sets to tally (unary) sets.

This talk will survey the area as well as describing recent joint research with Harry Buhrman, Steve Fenner, Dieter van Melkebeek and the speaker. The research was done while the speaker was at the University of Chicago.

The Capital Area Theory Symposia is an NSF sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department and UMIACS. NSF support under grant CCR-9732907 is gratefully acknowledged