Workshop on:
Complexity of Proofs and Computations

December 10, 2000 - December 16, 2000

Open problems asked by participants

Lance Fortnow, NEC Research

We are given an array of n^2 rows and n columns of variables whose values will take on {-1, 1}.  Does
there exist n polynomials p1,...,pn of degree n^1 over all the variables, such that for all such setting of
the array, sign (p1) ... sign (pn) differs from each row in at least one position?

Open problems by Jan Krajicek, Mathematical Institute of Academy of Sciences of the Czech Republic

Alasdair Urquhart, 

The relationship between regular and unrestricted resolution is still not very well understood.
Andreas Goerdt has proved that unrestricted resolution has a quasi-polynomial speedup over regular resolution
(SIAM J. Computing, Vol. 22 1993, 661-683). His proof is quite complicated and difficult.

Problem 1: Find a simpler and cleaner proof of the result.

Problem 2: Improve the speedup, if possible.

The examples used by Goerdt are rather elaborate. This suggests that for simpler examples, regular refutations are minimal.
Problem 3: Prove or refute this conjecture for well known families of examples, such as the Tseitin graph clauses or the pigeonhole
clauses.

Last updated 20 Feb 2001