TR94-006 Authors: Alexander Razborov

Publication: 12th December 1994 00:00

Downloads: 3521

Keywords:

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.