NP Might Not Be As Easy As Detecting Unique Solutions

Title: NP Might Not Be As Easy As Detecting Unique Solutions

Authors: Richard Beigel, Harry Buhrman, and Lance Fortnow

Abstract: We construct an oracle A such that

P^A = PARITYP^A and NP^A = EXP^A. This relativized world has several amazing properties:

The oracle A gives the first relativized world where one can solve satisfiability on formulae with at most one assignment yet P ≠ NP.
The oracle A is the first where P^A = UP^A ≠ NP^A = co-NP^A.
The construction gives a much simpler proof than that of Fenner, Fortnow and Kurtz of a relativized world where all the NP-complete sets are polynomial-time isomorphic. It is the first such computable oracle.
Relative to A we have a collapse of PARITYEXP^A ⊆ ZPP^A ⊆ P^A/poly.

We also create a different relativized world where there exists a set L in NP that is NP-complete under reductions that make one query to L but not complete under traditional many-one reductions. This contrasts with the result of Buhrman, Spaan and Torenvliet showing that these two completeness notions for NEXP coincide.

Download Full Paper