THE P VERSUS NP PROBLEM [PvsNPproblem]

THE P VERSUS NP PROBLEM

[PvsNPproblem]

Problem Statement. Does P = NP?

Proposition 1 

(a) If L1 ≤p L2 and L2 ∈ P, then L1 ∈ P. 

(b) If L1 is NP-complete, L2 ∈ NP and L1 ≤p L2, then L2 is NP-complete 

(c) If L is NP-complete and L ∈ P, then P=NP.

Proposition 2 

If P ⊆ LINEAR-SIZE, then P ≠ NP. 

This proposition could be interpreted as a method of proving P ≠ NP, but a more usual belief is that the hypothesis is false. 

Proposition 3 

If A then BPP = P. 

If not A then P ≠ NP. 

It should be pointed out that Proposition 3 relativizes, and, in particular, relative to any PSPACE-complete oracle Assertion A holds and BPP = P = NP. Thus a nonrelativizing construction will be needed if one is to prove P ≠ NP by giving small circuits for languages in E. Nonrelativizing constructions have been used successfully before, for example in showing IP (Interactive Polynomial time) contains all of PSPSACE. In this and other such constructions a key technique is to represent Boolean functions by multivariate polynomials over finite fields.