On provably disjoint NP-pairs
DOI:
https://doi.org/10.7146/brics.v1i36.21607Abstract
In this paper we study the pairs (U,V) of disjoint NP-sets representable in a theory T of Bounded Arithmetic in the sense that T proves U intersection V = \emptyset. For a large variety of theories T we exhibit a natural disjoint NP-pair which is complete for the class of disjoint 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 [1]. Namely, in order to prove the independence result from a theory T, it is sufficient to separate the corresponding complete NP-pair by a (quasi)poly-time computable set. We remark that such a separation is obvious for the theory S(S_2) + S Sigma^b_2 - PIND considered in [1], and this gives an alternative proof of the main result from that paper.[1] A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of Bounded Arithmetic. To appear in Izvestiya of the RAN, 1994.
Downloads
Published
1994-11-30
How to Cite
Razborov, A. A. (1994). On provably disjoint NP-pairs. BRICS Report Series, 1(36). https://doi.org/10.7146/brics.v1i36.21607
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.