Razborov~\cite{Razborov96} recently proved that polynomial calculus proofs of the pigeonhole principle $PHP_n^m$ must have degree at least $\ceiling{n/2}+1$ over any field. We present a simplified proof of the same result. The main idea of our proof is the same as in the original proof of Razborov: we want to describe ... more >>>

We present the best known separation between tree-like and general resolution, improving on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}. This is done by constructing a natural family of contradictions, of size $n$, that have $O(n)$-size resolution refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations. This result implies that the most ... more >>>

We consider some problems about pairs of disjoint $NP$ sets. The theory of these sets with a natural concept of reducibility is, on the one hand, closely related to the theory of proof systems for propositional calculus, and, on the other, it resembles the theory of NP completeness. Furthermore, such ... more >>>