Abstract:
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.