Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR94-006 | 12th December 1994 00:00

On provably disjoint NP-pairs


Authors: Alexander Razborov
Publication: 12th December 1994 00:00
Downloads: 3521


In this paper we study the pairs $(U,V)$ of disjoint ${\bf NP}$-sets
representable in a theory $T$ of Bounded Arithmetic in the sense that
$T$ proves $U\cap V=\emptyset$. For a large variety of theories $T$
we exhibit a natural disjoint ${\bf NP}$-pair which is complete for the
class of disjoint ${\bf NP}$-pairs representable in $T$. This allows us to
clarify the approach to showing independence of central open questions in
Boolean complexity from theories of Bounded Arithmetic initiated
in \cite{ind}. Namely, in order to prove the independence result
from a theory $T$, it is sufficient to separate the corresponding
complete ${\bf NP}$-pair by a (quasi)poly-time computable set. We remark
that such a separation is obvious for the theory $\scr S(S_2)+\scr S
\Sigma_2^b-PIND$ considered in \cite{ind}, and this gives an
alternative proof of the main result from that paper.

ISSN 1433-8092 | Imprint