ECCC-Report TR94-006https://eccc.weizmann.ac.il/report/1994/006Comments and Revisions published for TR94-006en-usMon, 12 Dec 1994 00:00:00 +0200
Paper TR94-006
| On provably disjoint NP-pairs |
Alexander Razborov
https://eccc.weizmann.ac.il/report/1994/006In 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.
Mon, 12 Dec 1994 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/006