The p versus np problem stephen cook



Yüklə 138.92 Kb.

tarix05.12.2017
ölçüsü138.92 Kb.


THE P VERSUS NP PROBLEM

STEPHEN COOK

1. Statement of the Problem

The P versus NP problem is to determine whether every language accepted

by some nondeterministic algorithm in polynomial time is also accepted by some

(deterministic) algorithm in polynomial time. To define the problem precisely it

is necessary to give a formal model of a computer. The standard computer model

in computability theory is the Turing machine, introduced by Alan Turing in 1936

[37]. Although the model was introduced before physical computers were built, it

nevertheless continues to be accepted as the proper computer model for the purpose

of defining the notion of computable function.

Informally the class P is the class of decision problems solvable by some algorithm

within a number of steps bounded by some fixed polynomial in the length of the

input. Turing was not concerned with the efficiency of his machines, rather his

concern was whether they can simulate arbitrary algorithms given sufficient time. It

turns out, however, Turing machines can generally simulate more efficient computer

models (for example, machines equipped with many tapes or an unbounded random

access memory) by at most squaring or cubing the computation time. Thus P is a

robust class and has equivalent definitions over a large class of computer models.

Here we follow standard practice and define the class P in terms of Turing machines.

Formally the elements of the class P are languages. Let Σ be a finite alphabet

(that is, a finite nonempty set) with at least two elements, and let Σ

be the set



of finite strings over Σ. Then a language over Σ is a subset L of Σ

. Each Turing



machine M has an associated input alphabet Σ. For each string w in Σ

there is



a computation associated with M with input w. (The notions of Turing machine

and computation are defined formally in the appendix.) We say that M accepts w

if this computation terminates in the accepting state. Note that M fails to accept

w either if this computation ends in the rejecting state, or if the computation fails

to terminate. The language accepted by M , denoted L(M ), has associated alphabet

Σ and is defined by

L(M ) = {w ∈ Σ

| M accepts w}.



We denote by t

M

(w) the number of steps in the computation of M on input w (see



the appendix). If this computation never halts, then t

M

(w) = ∞. For n ∈ N we



denote by T

M

(n) the worst case run time of M ; that is,



T

M

(n) = max{t



M

(w) | w ∈ Σ

n

},

where Σ



n

is the set of all strings over Σ of length n. We say that M runs in

polynomial time if there exists k such that for all n, T

M

(n) ≤ n



k

+ k. Now we

1



2

STEPHEN COOK

define the class P of languages by

P = {L | L = L(M ) for some Turing machine M that runs

in polynomial time}.

The notation NP stands for “nondeterministic polynomial time”, since originally

NP was defined in terms of nondeterministic machines (that is, machines that

have more than one possible move from a given configuration). However, now it is

customary to give an equivalent definition using the notion of a checking relation,

which is simply a binary relation R ⊆ Σ

× Σ


1

for some finite alphabets Σ and Σ



1

.

We associate with each such relation R a language L



R

over Σ ∪ Σ

1

∪ {#} defined



by

L

R



= {w#y | R(w, y)}

where the symbol # is not in Σ. We say that R is polynomial-time iff L

R

∈ P.


Now we define the class NP of languages by the condition that a language L

over Σ is in NP iff there is k ∈ N and a polynomial-time checking relation R such

that for all w ∈ Σ

,



w ∈ L ⇐⇒ ∃y(|y| ≤ |w|

k

and R(w, y)),



where |w| and |y| denote the lengths of w and y, respectively.

Problem Statement. Does P = NP?

It is easy to see that the answer is independent of the size of the alphabet Σ (we

assume |Σ| ≥ 2), since strings over an alphabet of any fixed size can be efficiently

coded by strings over a binary alphabet. (For |Σ| = 1 the problem is still open,

although it is possible that P = NP in this case but not in the general case.)

It is trivial to show that P ⊆ NP, since for each language L over Σ, if L ∈ P

then we can define the polynomial-time checking relation R ⊆ Σ

∪ Σ


by

R(w, y) ⇐⇒ w ∈ L



for all w, y ∈ Σ

.



Here are two simple examples, using decimal notation to code natural numbers:

The set of perfect squares is in P, since Newton’s method can be used to efficiently

approximate square roots. The set of composite numbers is in NP, where (denoting

the decimal notation for a natural number c by c) the associated polynomial time

checking relation R is given by

(1)


R(a, b) ⇐⇒ 1 < b < a and b|a.

(Recently it was shown that in fact the set of composite numbers is also in P [1],

answering a longstanding open question.)

2. History and Importance

The importance of the P vs NP question stems from the successful theories of

NP-completeness and complexity-based cryptography, as well as the potentially

stunning practical consequences of a constructive proof of P = NP.

The theory of NP-completeness has its roots in computability theory, which

originated in the work of Turing, Church, G¨

odel, and others in the 1930s. The

computability precursors of the classes P and NP are the classes of decidable and

c.e. (computably enumerable) languages, respectively. We say that a language L is

c.e. (or semi-decidable) iff L = L(M ) for some Turing machine M . We say that L



THE P VERSUS NP PROBLEM

3

is decidable iff L = L(M ) for some Turing machine M that satisfies the condition



that M halts on all input strings w. There is an equivalent definition of c.e. that

brings out its analogy with NP, namely L is c.e. iff there is a computable “checking

relation” R(x, y) such that L = {x | ∃yR(x, y)}.

Using the notation M to denote a string describing a Turing machine M , we

define the Halting Problem HP as follows:

HP = { M | M is a Turing machine that halts on input M }.

Turing used a simple diagonal argument to show that HP is not decidable. On the

other hand, it is not hard to show that HP is c.e.

Of central importance in computability theory is the notion of reducibility, which

Turing defined roughly as follows: A language L

1

is Turing reducible to a language



L

2

iff there is an oracle Turing machine M that accepts L



1

, where M is allowed to

make membership queries of the form x ∈ L

2

, which are correctly answered by an



“oracle” for L

2

. Later, the more restricted notion of many-one reducibility (≤



m

)

was introduced and defined as follows.



Definition 1. Suppose that L

i

is a language over Σ



i

, i = 1, 2. Then L

1



m



L

2

iff



there is a (total) computable function f : Σ

1



→ Σ

2



such that x ∈ L

1

⇐⇒ f (x) ∈ L



2

,

for all x ∈ Σ



1

.



It is easy to see that if L

1



m

L

2



and L

2

is decidable, then L



1

is decidable.

This fact provides an important tool for showing undecidability; for example, if

HP ≤


m

L, then L is undecidable.

The notion of NP-complete is based on the following notion from computability

theory:


Definition 2. A language L is c.e.-complete iff L is c.e., and L ≤

m

L for every



c.e. language L .

It is easy to show that HP is c.e.-complete. It turns out that most “natural”

undecidable c.e. languages are, in fact, c.e.-complete. Since ≤

m

is transitive, to



show that a c.e. language L is c.e.-complete it suffices to show that HP ≤

m

L.



The notion of polynomial-time computation was introduced in the 1960s by Cob-

ham [8] and Edmonds [13] as part of the early development of computational com-

plexity theory (although earlier von Neumann [38], in 1953, distinguished between

polynomial-time and exponential-time algorithms). Edmonds called polynomial-

time algorithms “good algorithms” and linked them to tractable algorithms.

It has now become standard in complexity theory to identify polynomial-time

with feasible, and here we digress to discuss this point. It is of course not literally

true that every polynomial-time algorithm can be feasibly executed on small inputs;

for example, a computer program requiring n

100


steps could never be executed on

an input even as small as n = 10. Here is a more defensible statement (see [10]):

Feasibility Thesis. A natural problem has a feasible algorithm iff it has a poly-

nomial-time algorithm.

Examples of natural problems that have both feasible and polynomial-time al-

gorithms abound: Integer arithmetic, linear algebra, network flow, linear program-

ming, many graph problems (connectivity, shortest path, minimum spanning tree,

bipartite matching), etc. On the other hand, the deep results of Robertson and

Seymour [29] provide a potential source of counterexamples to the thesis: They



4

STEPHEN COOK

prove that every minor-closed family of graphs can be recognized in polynomial

time (in fact, in time O(n

3

)), but the algorithms supplied by their method have



such huge constants that they are not feasible. However, each potential counterex-

ample can be removed by finding a feasible algorithm for it. For example, a feasible

recognition algorithm is known for the class of planar graphs, but none is currently

known for the class of graphs embeddable in R

3

with no two cycles linked. (Both



examples are minor-closed families.) Of course the words “natural” and “feasible”in

the thesis above should be explained; generally we do not consider a class with a

parameter as natural, such as the set of graphs embeddable on a surface of genus

k, k > 1.

We mention two concerns related to the “only if” direction of the thesis. The

first comes from randomized algorithms. We discuss at the end of Section 3 the

possibility that a source of random bits might be used to greatly reduce the recog-

nition time required for some language. Note, however, that it is not clear whether

a truly random source exists in nature. The second concern comes from quan-

tum computers. This computer model incorporates the idea of superposition of

states from quantum mechanics and allows a potential exponential speed-up of

some computations over Turing machines. For example, Shor [32] has shown that

some quantum computer algorithm is able to factor integers in polynomial time,

but no polynomial-time integer-factoring algorithm is known for Turing machines.

Physicists have so far been unable to build a quantum computer that can handle

more than a half-dozen bits, so this threat to the feasibility thesis is hypothetical

at present.

Returning to the historical treatment of complexity theory, in 1971 the present

author [9] introduced a notion of NP-completeness as a polynomial-time analog of

c.e.-completeness, except that the reduction used was a polynomial-time analog of

Turing reducibility rather than of many-one reducibility. The main results in [9] are

that several natural problems, including Satisfiability and 3-SAT (defined below)

and subgraph isomorphism are NP-complete. A year later Karp [21] used these

completeness results to show that 20 other natural problems are NP-complete,

thus forcefully demonstrating the importance of the subject. Karp also introduced

the now standard notation P and NP and redefined NP-completeness using the

polynomial-time analog of many-one reducibility, a definition that has become stan-

dard. Meanwhile Levin [23], independently of Cook and Karp, defined the notion

of “universal search problem”, similar to the NP-complete problem, and gave six

examples, including Satisfiability.

The standard definitions concerning NP-completeness are close analogs of Defi-

nitions 1 and 2 above.

Definition 3. Suppose that L

i

is a language over Σ



i

, i = 1, 2. Then L

1



p



L

2

(L



1

is p-reducible to L

2

) iff there is a polynomial-time computable function f : Σ



1

→ Σ



2

such that x ∈ L



1

⇐⇒ f (x) ∈ L

2

, for all x ∈ Σ



1

.



Definition 4. A language L is NP-complete iff L is in NP, and L ≤

p

L for every



language L in NP.

The following proposition is easy to prove: Part (b) uses the transitivity of ≤

p

,

and part (c) follows from part (a).



Proposition 1. (a) If L

1



p

L

2



and L

2

∈ P, then L



1

∈ P.


(b) If L

1

is NP-complete, L



2

∈ NP, and L

1



p



L

2

, then L



2

is NP-complete.




THE P VERSUS NP PROBLEM

5

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



Notice that parts (a) and (b) have close analogs in computability theory. The

analog of part (c) is simply that if L is c.e.-complete then L is undecidable. Part

(b) is the basic method for showing new problems are NP-complete, and part (c)

explains why it is probably a waste of time looking for a polynomial-time algorithm

for an NP-complete problem.

In practice, a member of NP is expressed as a decision problem, and the corre-

sponding language is understood to mean the set of strings coding YES instances

to the decision problem using standard coding methods. Thus the problem Satisfi-

ability is: Given a propositional formula F , determine whether F is satisfiable. To

show that this is in NP, we define the polynomial-time checking relation R(x, y),

which holds iff x codes a propositional formula F and y codes a truth assignment

to the variables of F that makes F true. This problem was shown in [9] to be

NP-complete essentially by showing that, for each polynomial-time Turing ma-

chine M that recognizes a checking relation R(x, y) for an NP language L, there is

a polynomial-time algorithm that takes as input a string x and produces a proposi-

tional formula F

x

(describing the computation of M on input (x, y), with variables



representing the unknown string y) such that F

x

is satisfiable iff M accepts the



input (x, y) for some y with |y| ≤ |x|

O(1)


.

An important special case of Satisfiability is 3-SAT, which was also shown to be

NP-complete in [9]. Instances of 3-SAT are restricted to formulas in conjunctive

normal form with three literals per clause. For example, the formula

(2)

(P ∨ Q ∨ R) ∧ ( ¯



P ∨ Q ∨ ¯

R) ∧ (P ∨ ¯

Q ∨ S) ∧ ( ¯

P ∨ ¯


R ∨ ¯

S)

is a YES instance to 3-SAT since the truth assignment τ satisfies the formula, where



τ (P ) = τ (Q) = T rue and τ (R) = τ (S) = F alse.

Many hundreds of NP-complete problems have been identified, including Sub-

setSum (given a set of positive integers presented in decimal notation, and a target

T, is there a subset summing to T?), many graph problems (given a graph G, does

G have a Hamiltonian cycle? Does G have a clique consisting of half of the vertices?

Can the vertices of G be colored with three colors with distinct colors for adjacent

vertices?). These problems give rise to many scheduling and routing problems with

industrial importance. The book [15] provides an excellent reference to the subject,

with 300 NP-complete problems listed in the appendix.

Associated with each decision problem in NP there is a search problem, which

is, given a string x, find a string y satisfying the checking relation R(x, y) for the

problem (or determine that x is a NO instance to the problem). Such a y is said to

be a certificate for x. In the case of an NP-complete problem it is easy to see that

the search problem can be efficiently reduced to the corresponding decision problem.

In fact, if P = NP, then the associated search problem for every NP problem has

a polynomial-time algorithm. For example, an algorithm for the decision problem

Satisfiability can be used to find a truth assignment τ satisfying a given satisfiable

formula F by, for each variable P in F in turn, setting P to True in F or False in

F , whichever case keeps F satisfiable.

The set of complements of NP languages is denoted coNP. The complement of

an NP-complete language is thought not to be in NP; otherwise NP = coNP.

The set TAUT of tautologies (propositional formulas true under all assignments) is

the standard example of a coNP-complete language. The conjecture NP = coNP



6

STEPHEN COOK

is equivalent to the assertion that no formal proof system (suitably defined) for

tautologies has short (polynomial-bounded) proofs for all tautologies [12]. This fact

has motivated the development of a rich theory of propositional proof complexity

[22], one of whose goals is to prove superpolynomial lower bounds on the lengths

of proofs for standard propositional proof systems.

There are interesting examples of NP problems not known to be either in P

or NP-complete.

One example is the graph isomorphism problem: Given two

undirected graphs, determine whether they are isomorphic.

Another example, until recently, was the set of composite numbers. As men-

tioned in the first section, this set is in NP, with checking relation (1), but it is

now known also to be in P [1]. However, the search problem associated with the

checking relation (1) is equivalent to the problem of integer factoring and is thought

unlikely to be solvable in polynomial time. In fact, an efficient factoring algorithm

would break the RSA public key encryption scheme [28] commonly used to allow

(presumably) secure financial transactions over the Internet.

There is an NP decision problem with complexity equivalent to that of integer

factoring, namely

L

fact


= { a, b | ∃d(1 < d < a and d|b)}.

Given an integer b > 1, the smallest prime divisor of b can be found with about

log

2

b queries to L



fact

, using binary search. It is easy to see that the complement of

L

fact


is also in NP: a certificate showing a, b is not in L

fact


could be the complete

prime decomposition of b. Thus L

fact

is a good example of a problem in NP that



seems unlikely to be either in P or NP-complete.

Computational complexity theory plays an important role in modern cryptog-

raphy [16]. The security of the Internet, including most financial transactions,

depends on complexity-theoretic assumptions such as the difficulty of integer fac-

toring or of breaking DES (the Data Encryption Standard). If P = NP, these

assumptions are all false.

Specifically, an algorithm solving 3-SAT in n

2

steps



could be used to factor 200-digit numbers in a few minutes.

Although a practical algorithm for solving an NP-complete problem (showing P

= NP) would have devastating consequences for cryptography, it would also have

stunning practical consequences of a more positive nature, and not just because of

the efficient solutions to the many NP-hard problems important to industry. For

example, it would transform mathematics by allowing a computer to find a formal

proof of any theorem that has a proof of reasonable length, since formal proofs can

easily be recognized in polynomial time. Such theorems may well include all of the

CMI prize problems. Although the formal proofs may not be initially intelligible

to humans, the problem of finding intelligible proofs would be reduced to that

of finding a recognition algorithm for intelligible proofs. Similar remarks apply

to diverse creative human endeavors, such as designing airplane wings, creating

physical theories, or even composing music. The question in each case is to what

extent an efficient algorithm for recognizing a good result can be found. This is a

fundamental problem in artificial intelligence, and one whose solution itself would

be aided by the NP-solver by allowing easy testing of recognition theories.

Even if P = NP it may still happen that every NP problem is susceptible

to a polynomial-time algorithm that works on “most” inputs. This could render

cryptography impossible and bring about most of the benefits of a world in which

P = NP. This also motivates Levin’s theory [24], [18] of average case completeness,




THE P VERSUS NP PROBLEM

7

in which the P = NP question is replaced by the question of whether every NP



problem with any reasonable probability distribution on its inputs can be solved in

polynomial time on average.

In [34] Smale lists the P vs NP question as problem 3 of mathematical problems

for the next century. However, Smale is interested not only in the classical version

of the question, but also in a version expressed in terms of the field of complex

numbers. Here Turing machines must be replaced by a machine model that is

capable of doing exact arithmetic and zero tests on arbitrary complex numbers.

The P vs NP question is replaced by a question related to Hilbert’s Nullstellensatz:

Is there a polynomial-time algorithm that, given a set of k multivariate polynomials

over C, determines whether they have a common zero? See [4] for a development

of complexity theory in this setting.

The books by Papadimitriou [25] and Sipser [33] provide good introductions to

mainstream complexity theory.

3. The Conjecture and Attempts to Prove It

Most complexity theorists believe that P = NP. Perhaps this can be partly

explained by the potentially stunning consequences of P = NP mentioned above,

but there are better reasons. We explain these by considering the two possibilities

in turn: P = NP and P = NP.

Suppose first that P = NP and consider how one might prove it. The obvi-

ous way is to exhibit a polynomial-time algorithm for 3-SAT or one of the other

thousand or so known NP-complete problems, and, indeed, many false proofs have

been presented in this form. There is a standard toolkit available [7] for devising

polynomial-time algorithms, including the greedy method, dynamic programming,

reduction to linear programming, etc. These are the subjects of a course on algo-

rithms, typical in undergraduate computer science curriculums. Because of their

importance in industry, a vast number of programmers and engineers have at-

tempted to find efficient algorithms for NP-complete problems over the past 30

years, without success. There is a similar strong motivation for breaking the cryp-

tographic schemes that assume P = NP for their security.

Of course, it is possible that some nonconstructive argument, such as the Robert-

son–Seymour proofs mentioned earlier in conjunction with the Feasibility Thesis,

could show that P = NP without yielding any feasible algorithm for the standard

NP-complete problems. At present, however, the best proven upper bound on

an algorithm for solving 3-SAT is approximately 1.5

n

, where n is the number of



variables in the input formula.

Suppose, on the other hand, that P = NP, and consider how one might prove it.

There are two general methods that have been tried: diagonalization with reduction

and Boolean circuit lower bounds.

The method of diagonalization with reduction has been used very successfully

in computability theory to prove a host of problems undecidable, beginning with

the Halting Problem. It has also been used successfully in complexity theory to

prove super-exponential lower bounds for very hard decidable problems. For ex-

ample, Presburger arithmetic, the first-order theory of integers under addition, is a

decidable theory for which Fischer and Rabin [14] proved that any Turing machine

deciding the theory must use at least 2

2

cn



steps in the worst case, for some c > 0.

In general, lower bounds using diagonalization and reduction relativize; that is,




8

STEPHEN COOK

they continue to apply in a setting in which both the problem instance and the

solving Turing machine can make membership queries to an arbitrary oracle set

A. However, in [3] it was shown that there is an oracle set A relative to which P

= NP, suggesting that diagonalization with reduction cannot be used to separate

these two classes. (There are nonrelativizing results in complexity theory, as will

be mentioned below.) It is interesting to note that relative to a generic oracle, P

= NP [5, 11].

A Boolean circuit is a finite acyclic graph in which each non-input node, or gate,

is labelled with a Boolean connective; typically from {AND , OR, NOT}. The input

nodes are labeled with variables x

1

, ..., x


n

, and for each assignment of 0 or 1 to each

variable, the circuit computes a bit value at each gate, including the output gate,

in the obvious way. It is not hard to see that if L is a language over {0, 1} that

is in P, then there is a polynomial-size family of Boolean circuits B

n

such that



B

n

has n inputs, and for each bit string w of length n, when w is applied to the



n input nodes of B

n

, then the output bit of B



n

is 1 iff w ∈ L. In this case we say

that B

n

computes L.



Thus to prove P = NP it suffices to prove a super-polynomial lower bound on the

size of any family of Boolean circuits solving some specific NP-complete problem,

such as 3-SAT. Back in 1949 Shannon [31] proved that for almost all Boolean

functions f : {0, 1}

n

→ {0, 1}, any Boolean circuit computing f requires at least



2

n

/n gates. Unfortunately, his counting argument gives no clue as to how to prove



lower bounds for problems in NP. Exponential lower bounds for NP problems have

been proved for restricted circuit models, including monotone circuits [26], [2] and

bounded depth circuits with unbounded fan-in gates [17], [35] (see [6]). However,

all attempts to find even super-linear lower bounds for unrestricted Boolean circuits

for “explicitly given” Boolean functions have met with total failure; the best such

lower bound proved so far is about 4n. Razborov and Rudich [27] explain this

failure by pointing out that all methods used so far can be classified as “natural

proofs”, and natural proofs for general circuit lower bounds are doomed to failure,

assuming a certain complexity-theoretic conjecture asserting that strong pseudo-

random number generators exist.

Since such generators have been constructed

assuming the hardness of integer factorization, we can infer the surprising result

that a natural proof for a general circuit lower bound would give rise to a more

efficient factoring algorithm than is currently known.

The failure of complexity theory to prove interesting lower bounds on a general

model of computation is much more pervasive than the failure to prove P = NP.

It is consistent with present knowledge that not only could Satisfiability have a

polynomial-time algorithm, it could have a linear time algorithm on a multitape

Turing machine. The same applies for all 21 problems mentioned in Karp’s original

paper [21]. There are complexity class separations that we know exist but cannot

prove. For example, consider the sequence of complexity class inclusions

LOGSPACE ⊆ P⊆ NP⊆ PSPACE .

A simple diagonal argument shows that the first is a proper subset of the last, but

we cannot prove any particular adjacent inclusion is proper.

As another example, let LINEAR-SIZE be the class of languages over {0, 1}

that can be computed by a family B

n

of Boolean circuits of size O(n). It is not



known whether either P or NP is a subset of LINEAR-SIZE, although Kannan

[20] proved that there are languages in the polynomial hierarchy (a generalization of




THE P VERSUS NP PROBLEM

9

NP) not in LINEAR-SIZE. Since if P = NP, the polynomial hierarchy collapses



to P, we have

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.

A fundamental question in complexity theory is whether a source of random bits

can be used to speed up substantially the recognition of some languages, provided

one is willing to accept a small probability of error. The class BPP consists of all

languages L that can be recognized by a randomized polynomial-time algorithm,

with at most an exponentially small error probability on every input. Of course

P ⊆ BPP, but it is not known whether the inclusion is proper. The set of prime

numbers is in BPP [36], but it is not known to be in P. A reason for thinking that

BPP = P is that randomized algorithms are often successfully executed using a

deterministic pseudo-random number generator as a source of “random” bits.

There is an indirect but intriguing connection between the two questions P =

BPP and P = NP. Let E be the class of languages recognizable in exponential

time; that is the class of languages L such that L = L(M ) for some Turing machine

M with T

M

(n) = O(2



cn

) for some c > 0. Let A be the assertion that some language

in E requires exponential circuit complexity. That is,

Assertion A. There is L ∈ E and

> 0 such that, for every circuit family B

n

computing L and for all sufficiently large n, B



n

has at least 2

n

gates.


Proposition 3. If A then BPP = P. If not A then P = NP.

The first implication is a lovely theorem by Impagliazzo and Wigderson [19] and

the second is an intriguing observation by V. Kabanets that strengthens Proposi-

tion 2. In fact, Kabanets concludes P = NP from a weaker assumption than not

A; namely that every language in E can be computed by a Boolean circuit family

B

n



such that for at least one n, B

n

has fewer gates than the maximum needed to



compute any Boolean function f : {0, 1}

n

→ {0, 1}. But there is no consensus on



whether this hypothesis is true.

We should point 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 suc-

cessfully before, for example in showing IP (Interactive Polynomial time) contains

all of PSPSACE [30]. In this and other such constructions a key technique is to

represent Boolean functions by multivariate polynomials over finite fields.

Appendix: Definition of Turing Machine

A Turing machine M consists of a finite state control (i.e., a finite program)

attached to a read/write head moving on an infinite tape. The tape is divided into

squares, each capable of storing one symbol from a finite alphabet Γ that includes

the blank symbol b. Each machine M has a specified input alphabet Σ, which is a

subset of Γ, not including the blank symbol b. At each step in a computation, M is

in some state q in a specified finite set Q of possible states. Initially, a finite input

string over Σ is written on adjacent squares of the tape, all other squares are blank

(contain b), the head scans the left-most symbol of the input string, and M is in



10

STEPHEN COOK

the initial state q

0

. At each step M is in some state q and the head is scanning a



tape square containing some tape symbol s, and the action performed depends on

the pair (q, s) and is specified by the machine’s transition function (or program) δ.

The action consists of printing a symbol on the scanned square, moving the head

left or right one square, and assuming a new state.

Formally, a Turing machine M is a tuple Σ, Γ, Q, δ , where Σ, Γ, Q are finite

nonempty sets with Σ ⊆ Γ and b ∈ Γ − Σ. The state set Q contains three special

states q

0

, q



accept

, q


reject

. The transition function δ satisfies

δ : (Q − {q

accept


, q

reject


}) × Γ → Q × Γ × {−1, 1}.

If δ(q, s) = (q , s , h), the interpretation is that, if M is in state q scanning the

symbol s, then q is the new state, s is the symbol printed, and the tape head

moves left or right one square depending on whether h is −1 or 1.

We assume that the sets Q and Γ are disjoint.

A configuration of M is a string xqy with x, y ∈ Γ

, y not the empty string, and



q ∈ Q.

The interpretation of the configuration xqy is that M is in state q with xy on

its tape, with its head scanning the left-most symbol of y.

If C and C are configurations, then C

M

→ C if C = xqsy and δ(q, s) = (q , s , h)



and one of the following holds:

C = xs q y and h = 1 and y is nonempty.

C = xs q b and h = 1 and y is empty.

C = x q as y and h = −1 and x = x a for some a ∈ Γ.

C = q bs y and h = −1 and x is empty.

A configuration xqy is halting if q ∈ {q

accept

, q


reject

}. Note that for each non-

halting configuration C there is a unique configuration C such that C

M

→ C .



The computation of M on input w ∈ Σ

is the unique sequence C



0

, C


1

, ... of


configurations such that C

0

= q



0

w (or C


0

= q


0

b if w is empty) and C

i

M

→ C



i+1

for


each i with C

i+1


in the computation, and either the sequence is infinite or it ends in

a halting configuration. If the computation is finite, then the number of steps is one

less than the number of configurations; otherwise the number of steps is infinite.

We say that M accepts w iff the computation is finite and the final configuration

contains the state q

accept


.

Acknowledgments

My thanks to Avi Wigderson and Hugh Woodin for many helpful suggestions

for improving an earlier version of this paper.

References

[1] M. Agrawal, N. Kayal, and N. Saxena, Primes is in P, Ann. Math. 160 (2004), 781–793.

[2] N. Alon and R.B. Boppana, The monotone circuit complexity of boolean functions, Combi-

natorica 7 (1987), 1–22.

[3] T. Baker, J. Gill, and R. Solovay, Relativizations of the P =? NP question, SICOMP: SIAM

Journal on Computing, 1975.

[4] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer-

Verlag, New York, 1998.

[5] M. Blum and R. Impagliazzo, Generic oracles and oracle classes, in Proceedings of the

28th Annual Symposium on Foundations of Computer Science, A.K. Chandra, ed., IEEE

Computer Society Press, Los Angeles, 1987, 118–126.



THE P VERSUS NP PROBLEM

11

[6] R.B. Boppana and M. Sipser, The complexity of finite functions, Handbook of Theoretical



Computer Science, Volume A: Algorithms and Complexity, J. Van Leeuwen, ed., Elsevier and

The MIT Press, Cambridge, MA, 1990, 759–804.

[7] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition,

McGraw Hill, New York, 2001.

[8] A. Cobham, The intrinsic computational difficulty of functions, in Proceedings of the 1964

International Congress for Logic, Methodology, and Philosophy of Science, Y. Bar-Hille, ed.,

Elsevier/North-Holland, Amsterdam, 1964, 24–30.

[9] S. Cook, The complexity of theorem-proving procedures, in Conference Record of Third An-

nual ACM Symposium on Theory of Computing, ACM, New York, 1971, 151–158.

[10] S. Cook, Computational complexity of higher type functions, in Proceedings of the Interna-

tional Congress of Mathematicians, Kyoto, Japan, Springer-Verlag, Berlin, 1991, 55–69.

[11] S. Cook, R. Impagliazzo, and T. Yamakami, A tight relationship between generic oracles and

type-2 complexity theory, Information and Computation 137 (1997), 159–170.

[12] S. Cook and R. Reckhow, The relative efficiency of propositional proof systems, J. Symbolic

Logic 44 (1979), 36–50.

[13] J. Edmonds, Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur.

Standards Sect. B 69 (1965), 67–72.

[14] M.J. Fischer and M.O. Rabin, Super-exponential complexity of Presburger arithmetic, in

Complexity of Computation 7, AMS, Providence, RI, 1974, 27–41.

[15] M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of NP-

Completeness, W.H. Freeman and Co., San Francisco, 1979.

[16] O. Goldreich, The Foundations of Cryptography — Volume 1, Cambridge University Press,

Cambridge, UK, 2000.

[17] J. Hastad, Almost optimal lower bounds for small depth circuits, in Randomness and Com-

putation, Advances in Computing Research 5, JAI Press Inc., Greenwich, CT, 1989, 143–170.

[18] R. Impagliazzo, A personal view of average-case complexity, in 10th IEEE Annual Conference

on Structure in Complexity Theory, IEEE Computer Society Press, Washington, DC, 1995,

134–147.


[19] R. Impagliazzo and A. Wigderson, P = BPP if E requires exponential circuits: Derandomizing

the XOR lemma, in ACM Symposium on Theory of Computing (STOC), ACM, New York,

1997, 220–229.

[20] R. Kannan, Circuit-size lower bounds and non-reducibility to sparse sets, Information and

Control 55 (1982), 40–56..

[21] R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Com-

putations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, 85–103.

[22] J. Krajicek, Bounded Arithmetic, Propositional Logic, and Complexity Theory, Cambridge

University Press, Cambridge, 1995.

[23] L. Levin, Universal search problems (in Russian), Problemy Peredachi Informatsii 9 (1973),

265–266. English translation in B. A. Trakhtenbrot, A survey of Russian approaches to Pere-

bor (brute-force search) algorithms, Annals of the History of Computing 6 (1984), 384-400.

[24] L. Levin, Average case complete problems, SIAM J. Computing 15 (1986), 285–286.

[25] C. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994.

[26] A.A. Razborov, Lower bounds on the monotone complexity of some boolean functions, Soviet

Math. Dokl. 31 (1985), 354–357.

[27] A.A. Razborov and S. Rudich, Natural proofs, Journal of Computer and System Sciences 55

(1997), 24–35.

[28] R.L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and

public-key cryptosystems, Comm. ACM 21 (1978), 120–126.

[29] N. Robertson and P.D. Seymour, Graph minors i-xiii, Journal of Combinatorial Theory B,

1983–1995.

[30] A. Shamir, IP = PSPACE, J.A.C.M. 39 (1992), 869–977.

[31] C. Shannon, The synthesis of two-terminal switching circuits, Bell System Technical Journal

28 (1949), 59–98.

[32] P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a

quantum computer, SIAM J. Computing 26 (1997), 1484–1509.

[33] M. Sipser, Introduction to the Theory of Computation, PWS Publ., Boston, 1997.




12

STEPHEN COOK

[34] S. Smale, Mathematical problems for the next century, Math. Intelligencer 20, no. 2, 1998,

7–15.


[35] R. Smolensky, Algebraic methods in the theory of lower bounds for boolean circuit complexity,

in ACM Symposium on Theory of Computing (STOC) 19, ACM, New York, 1987, 77-82.

[36] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM Journal on Com-

puting 6 (1977), 84–85.

[37] A. Turing, On computable numbers with an application to the entscheidnungsproblem, Proc.

London Math. Soc. 42 (1936), 230–265.

[38] J. von Neumann, A certain zero-sum two-person game equivalent to the optimal assignment

problem, in Contributions to the Theory of Games II, H.W. Kahn and A.W. Tucker, eds.



Princeton Univ. Press, Princeton, NJ, 1953, 5–12.



Dostları ilə paylaş:


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2017
rəhbərliyinə müraciət

    Ana səhifə