Abstract:
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 
. 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
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.
Available as PostScript, PDF, DVI.