This is the html version of the file http://www.claymath.org/prizeproblems/p_vs_np.pdf. G o o g l e automatically generates html versions of documents as we crawl the web. To link to or bookmark this page, use the following url: http://www.google.com/search?q=cache:qE-SjCZ8JJIC:www.claymath.org/prizeproblems/p_vs_np.pdf+NP+problem+&hl=pl&ie=UTF-8&inlang=pl Google is not affiliated with the authors of this page nor responsible for its content. These search terms have been highlighted:  np  problem

---

Page 1

The P versus NP Problem

Stephen Cook

University of Toronto

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 [Tur36]. 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, but rather his concern was whether they can simulate arbitrary

algorithms given sufficient time. However it turns out 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,

1

---

Page 2

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 define the class P of languages by

P = {L | L = L(M) for some Turing machine M which runs in polynomial time}

The notation NP stands for "nondeterministic polynomial time", since orig-

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

chines that have more than one possible move from a given configuration).

However now it is customary to give an equivalent definition using the no-

tion 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

2

---

Page 3

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 num-

bers: The set of perfect squares is in P and the set of composite numbers is

in NP (and not known to be in P). For the latter, the associated polynomial

time checking relation R is given by

R(a, b) 1 < b < a and b|a

(1)

In general the decimal notation for a natural number c is denoted by c.

2. History and Importance

The importance of the P vs NP questions stems from the successful theo-

ries 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 1930's.

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 is decidable iff L = L(M) for some Turing

machine M which satisfies the condition that M halts on all input strings

w. There is an equivalent definition of c.e. which 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 which halts on input M }

3

---

Page 4

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: Alanguage L

1

is Turing reducible

to a language L

2

iff there is an oracle Turing machine M which 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 computabil-

ity theory:

Definition 2: Alanguage 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 is suffices to show that

HP

m

L.

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

Cobham [Cob64] and Edmonds [Edm65] as part of the early development

of computational complexity theory (although earlier von Neumann [vN53]

in 1953 distinguished between polynomial time and exponential-time algo-

rithms). 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

4

---

Page 5

never be executed on an input even as small as n = 10. Here is a more

defensible statement (see [Coo91]):

Feasibility Thesis: Anatural problem has a feasible algorithm iff it has a

polynomial-time algorithm.

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

algorithms abound: Integer arithmetic, linear algebra, network flow, linear

programming, many graph problems (connectivity, shortest path, minimum

spanning tree, bipartite matching) etc. On the other hand the deep results of

Robertson and Seymour [RS95] provide a potential source of counterexamples

to the thesis: They 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 counter example 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 recognition 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 Quantum 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 ex-

ample, Shor [Sho97] 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. However 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

5

---

Page 6

present author [Coo71] 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 re-

ducibility. The main results in [Coo71] are that several natural problems, in-

cluding Satisfiability and 3-SAT (defined below) and subgraph isomorphism

are NP-complete. Ayear later Karp [Kar72] used these completeness re-

sults to show that 20 other natural problems are NP-complete, thus force-

fully 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 which has be-

come standard. Meanwhile Levin [Lev73] independently of Cook and Karp

defined the notion of "universal search problem", similar to NP-complete

problem, and gave six examples, including Satisfiability.

The standard definitions concerning NP-completeness are close analogs of

Definitions 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: Alanguage 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.

(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

6

---

Page 7

corresponding language is understood to mean the set of strings coding YES

instances to the decision problem using standard coding methods. Thus the

problem Satisfiability 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 which makes F

true. This problem was shown to be NP-complete in [Coo71] essentially by

showing that for each polynomial-time Turing machine M which recognizes

a checking relation R(x, y) for an NP language L, there is a polynomial-

time algorithm which takes as input a string x and produces a propositional

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 [Coo71]. Instances of 3-SAT are restricted to formulas

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

formula

(P Q R) ( ¯

P Q ¯

R) (P ¯

Q S) ( ¯

P ¯

R ¯

S)

(2)

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

SubsetSum (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

[GJ79] 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

7

---

Page 8

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 , which ever

case keeps F satisfiable.

The set of complements of NP languages is denoted coNP. The comple-

ment 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 lan-

guage. The conjecture NP = coNP is equivalent to the assertion that no

formal proof system (suitably defined) for tautologies has short (polynomial-

bounded) proofs for all tautologies [CR79]. This fact has motivated the

development of a rich theory of proportional proof complexity [Kra95], 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 set of composite numbers, mentioned in

the first section, with checking relation (1). Here it is conjectured that there

is no polynomial-time Turing reduction from the search problem (integer

factoring) to the decision problem. Specifically, Miller [Mil76] showed how to

determine in polynomial time whether a given number is composite, assuming

the Extended Riemann Hypothesis, but a polynomial-time integer factoring

algorithm is thought unlikely to exist. In fact an efficient factoring algorithm

would break the RSApublic key encryption scheme [ARS78] commonly used

to allow (presumably) secure financial transactions over the internet.

The complement of the set of composite numbers (essentially the set of

primes) was proved to be in NP by an interesting argument due to Pratt

[Pra75], and hence is unlikely to be NP-complete.

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

teger 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. Using Pratt's theorem, it is

8

---

Page 9

easy to see that the complement of L

fact

is also in NP: a certificate showing

a, b is a non-instance of L

fact

could be the complete prime decomposition

of b, together with Pratt certificates proving that each of the prime factors

is indeed prime. Thus it is considered unlikely that L

fact

is NP-complete.

Computational complexity theory plays an important role in modern cryp-

tography [Gol00]. The security of the internet, including most financial trans-

actions, depend on complexity-theoretic assumptions such as the difficulty of

integer factoring 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 (show-

ing 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 impor-

tant to industry. For example, it would transform mathematics by allowing

a computer to find a formal proof of any theorem which has a proof of rea-

sonable length, since formal proofs can easily be recognized in polynomial

time. Example 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 physi-

cal 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 it-

self 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 which 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 [Lev86, Imp95]

of average case completeness, 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 time polynomial on average.

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

9

---

Page 10

problems for the next century. However Smale is interested not just in the

classical version of the question, but also 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

which, given a set of k multivariate polynomials over C, determines whether

they have a common zero? See [BCSS98] for a development of complexity

theory in this setting, including the intriguing result that the Mandelbrot set

is undecidable.

The books by Papadimitriou [Pap94] and Sipser [Sip97] provide good intro-

ductions 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 obvious

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

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

been presented in this form. There is a standard toolkit available [CLR90]

for devising polynomial-time algorithms, including the greedy method, dy-

namic programming, reduction to linear programming, etc. These are the

subjects of a course on algorithms, typical in undergraduate computer sci-

ence curriculums. Because of their importance in industry, a vast number

of programmers and engineers have attempted to find efficient algorithms

for NP-complete problems over the past 30 years, without success. There

is similar strong motivation for breaking the cryptographic schemes which

assume P = NP for their security.

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

Roberton/Seymour proofs mentioned earlier in conjunction with the Feasibil-

ity Thesis, could show that P = NP without yielding any feasible algorithm

for the standard NP-complete problems. However at present the best proven

upper bound on an algorithm for solving 3-SAT is approximately 1.5

n

, where

10

---

Page 11

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: diagonaliza-

tion/reduction and Boolean circuit lower bounds.

The method of diaonalization 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 prob-

lems. For example, Presburger arithmetic, the first-order theory of integers

under addition, is a decidable theory for which Fischer and Rabin [FR74]

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 diago-

nalization and reduction relativize; that is 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 [BGS75] it was

shown that there is an oracle set A relative to which P = NP, suggesting

that diagonalization/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

[BI87, SCY97].

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, in-

cluding 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 [Sha49] 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

11

---

Page 12

bounds for NP problems have been proved for restricted circuit models, in-

cluding monotone circuits [Raz85, AB87] and bounded depth circuits with

unbounded fan-in gates [Has89, Smo87] (see [BS90]). 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 [RR97] 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 factor-

ization, 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 gen-

eral model of computation is much more pervasive than the failure to prove

P = NP. It is consistent with present knowledge that not only could Satis-

fiability have a polynomial-time algorithm, it could have a linear time algo-

rithm on a multitape Turing machine. The same applies for all 21 problems

mentioned in Karp's original paper [Kar72]. There are complexity class sep-

arations which we know exist but cannnot prove. For example, consider the

sequence of complexity class inclusions

LOGSPACE P NP PSPACE

Asimple diagonal arugment 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}

which 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 [Kan82] proved that there are languages in the polynomial

hierarchy (a generalization of NP) not in LINEAR-SIZE. Since if P = NP

then 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.

12

---

Page 13

Afundamental question in complexity theory is whether a source of random

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

provided one is willing to accept a small probability of error. The class

BPP consists of all languages L which can be recognized by a randomized

polynomial-time algorithm, with at most an exponentially small error prob-

ability 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 [SS77], but

it is not known to be in P. Areason 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

[IW97] and the second is an intriguing observation by V. Kabanets which

strengthens Proposition 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. However nonrelativizing

constructions have been used successfully before, for example in showing IP

(Interactive Polynomial time) contains all of PSPSACE [Sha92]. In this and

other such constructions a key technique is to represent Boolean functions

13

---

Page 14

by multivariate polynomials over finite fields.

Appendix: Definition of Turing machine

ATuring machine M consists of a finite state control (i.e. a finite program)

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

into squares, each capable of storing one symbol from a finite alphabet

which includes the blank symbol b. Each machine M has a specified input

alphabet , which is a subset of , not including the blank symbol b. A t

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 the initial state q

0

.

A t 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.

14

---

Page 15

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.

Aconfiguration 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

[AB87]

N. Alon and R. B. Boppana. The monotone circuit complexity of

boolean functions. Combinatorica, 7(1):1­22, 1987.

[ARS78] L. Adleman, R. L. Rivest, and A. Shamir. A method for obtaining

digital signature and public-key cryptosystems. Communication

of the ACM, 21(2), 1978.

[BCSS98] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real

Computation. Springer-Verlag, New York, 1998.

[BGS75] T. Baker, J. Gill, and R. Solovay. Relativizations of the P =? NP

question. SICOMP: SIAM Journal on Computing, 1975.

[BI87]

M. Blum and R. Impagliazzo. Generic oracles and oracle classes.

In Ashok K. Chandra, editor, Proceedings of the 28th Annual Sym-

posium on Foundations of Computer Science, pages 118­126, Los

Angeles, CA, October 1987. IEEE Computer Society Press.

15

---

Page 16

[BS90]

R. B. Boppana and M. Sipser. The complexity of finite functions.

In J. Van Leeuwen, editor, Handbook of Theoretical Computer Sci-

ence, Volume A: Algorithms and Complexity, pages 759­804. El-

sevier and The MIT Press, 1990.

[CLR90] T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algo-

rithms. McGraw Hill, New York, 1990.

[Cob64] A. Cobham. The intrinsic computational difficulty of functions. In

Yehoshua Bar-Hillel, editor, Proceedings of the 1964 International

Congress for Logic, Methodology, and Philosophy of Science, pages

24­30. Elsevier/North-Holland, 1964.

[Coo71] Stephen Cook. The complexity of theorem-proving procedures. In

Conference Record of Third Annual ACM Symposium on Theory

of Computing, pages 151­158, 1971.

[Coo91] Stephen Cook. Computational complexity of higher type func-

tions.

In Ichiro Satake, editor, Proceedings of the Interna-

tional Congress of Mathematicians, Kyoto, Japan, pages 55­69.

Springer­Verlag, 1991.

[CR79]

S. Cook and R. Reckhow. The relative efficiency of propositional

proof systems. J. Symbolic Logic, 44(1), 1979.

[Edm65] Jack Edmonds. Minimum partition of a matroid into independent

subsets. J. Res. Nat. Bur. Standards Sect. B, 69:67­72, 1965.

[FR74]

M. J. Fischer and M. O. Rabin. Super-exponential complexity of

Presburger arithmetic. In R. M. Karp, editor, Complexity of Com-

putation, volume 7, pages 27­41. American Mathematical Society,

Providence, RI, 1974.

[GJ79]

M. R. Garey and D. S. Johnson. Computers and Intractibility, a

Guide to the Theory of NP-Completeness. W.H. Freeman and Co.,

San Francisco, 1979.

[Gol00]

Oded Goldreich. The Foundations of Cryptography­Volume 1.

Cambridge University Press, 2000.

16

---

Page 17

[Has89]

J. Hastad. Almost optimal lower bounds for small depth circuits.

In S. Micali, editor, Randomness and Computation, Advances in

Computing Research, Vol. 5, pages 143­170. JAI Press Inc., 1989.

[Imp95] R. Impagliazzo. Apersonal view of average-case complexity. In

10th IEEE Annual Conference on Structure in Complexity Theory,

pages 134­147, 1995.

[IW97]

R. Impagliazzo and A. Wigderson. P = BPP if E requires expo-

nential circuits: Derandomizing the XOR lemma. In STOC: ACM

Symposium on Theory of Computing (STOC), 1997.

[Kan82] Ravi Kannan. Circuit-size lower bounds and non-reducibility to

sparse sets. Information and Control, 55:40­56, 1982.

[Kar72]

Richard M. Karp. Reducibility among combinatorial problems. In

R. E. Miller and J. W. Thatcher, editors, Complexity of Computer

Computations, pages 85­103, New York, 1972. Plenum Press.

[Kra95]

J. Krajicek. Bounded Arithmetic, Propositional Logic, and Com-

plexity Theory. Cambridge, 1995.

[Lev73]

L. Levin. Universal search problems (in russian)". Problemy

Peredachi Informatsii, 9(3):265­266, 1973. English translation in

Trakhtenbrot, B. A.: A survey of Russian approaches to Perebor

(brute-force search) algorithms. Annals of the History of Comput-

ing, 6 (1984), pages. 384-400.

[Lev86]

L. Levin. Average case complete problems. SIAM J. Computing,

15:285­286, 1986.

[Mil76]

G. L. Miller. Reimann's hypothesis and tests for primality. J.

Comput. System Sci, 13:300­317, 1976.

[Pap94]

Christos Papadimitriou. Computational Complexity. Addison­

Wesley, 1994.

[Pra75]

V. R. Pratt. Every prime has a succinct certificate. SIAM Journal

on Computing, 4(3):214­220, 1975.

17

---

Page 18

[Raz85]

Alexander A. Razborov. Lower bounds on the monotone complex-

ity of some boolean functions. Soviet Math. Dokl., 31:354­357,

1985.

[RR97]

Alexander A. Razborov and Steven Rudich. Natural proofs. Jour-

nal of Computer and System Sciences, 55(1):24­35, August 1997.

[RS95]

N. Robertson and P. D. Seymour. Graph minors i­xiii. Journal of

Combinatorial Theory B, 1983­1995.

[SCY97] R. Impagliazzo S. Cook and T. Yamakami. Atight relationship

between generic oracles and type-2 complexity theory. Information

and Computation, 137(2):159­170, 15 September 1997.

[Sha49]

C. Shannon. The synthesis of two­terminal switching circuits. Bell

System Technical Journal, 28:59­98, 1949.

[Sha92]

Adi Shamir. Ip = pspace. J.A.C.M., 39(4):869­877, 1992.

[Sho97]

Peter Shor. Polynomial-time algorithms for prime factorization

and discrete logarithms on a quantum computer. SIAM J. Com-

puting, 26:1484­1509, 1997.

[Sip97]

Michael Sipser. Introduction to the Theory of Computation. PWS,

1997.

[Sma98] Steve Smale. Mathematical problems for the next century. MATH-

INT: The Mathematical Intelligencer, 20, 1998.

[Smo87] R. Smolensky. Algebraic methods in the theory of lower bounds

for boolean circuit complexity. In ACM Symposium on Theory of

Computing (STOC), volume 19, pages 77­82, 1987.

[SS77]

R. Solovay and V. Strassen. Afast Monte-Carlo test for primality.

SIAM Journal on Computing, 6(1):84­85, March 1977.

[Tur36]

Alan Turing. On computable numbers with an application to the

entscheidnungsproblem. Proc. London Math. Soc. ser. 2, 42:230­

265, 1936-7.

18

---

Page 19

[vN53]

J. von Neumann. Acertain zero-sum two-person game equivalent

to the optimal assignment problem. In H. W. Kahn and A. W.

Tucker, editors, Contributions to the Theory of Games II. Prince-

ton Univ. Press, 1953.

19