P6 = NP (WAS: an oracle paradox)
- From: "http://alexslemonade.org @ http://MeAmI.org" <marty.musatov@xxxxxxxxx>
- Date: Wed, 21 Oct 2009 04:35:08 -0700 (PDT)
On Oct 21, 4:24 am, scarlett <durco...@xxxxxxxxx> wrote:
Actually Oracle has many paradox but it is still mainly used. The word mean of Oracle is prophet. The definitions of oracle are,
* noun: a shrine where an oracular god is consulted
* noun: a prophecy (usually obscure or allegorical) revealed by a priest or priestess; believed to be infallible
* noun: an authoritative person who divines the future
for more infohttp://center2info.com/oracle.aspx
This is the html version of the file http://www.cs.toronto.edu/~sacook/homepage/PvsNP.ps.
Google automatically generates html versions of documents as we crawl
the web.
Page 1
The P versus NP ProblemStephen CookUniversity of Toronto1. Statement
of the ProblemThe P versus NP problem is to determine whether every
language accepted by some nonde-terministic algorithm in polynomial
time is also accepted by some (deterministic) algorithmin polynomial
time. To de ne the problem precisely it is necessary to give a formal
model ofa 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 phys-ical computers
were built, it nevertheless continues to be accepted as the proper
computermodel for the purpose of de ning the notion of computable
function.Informally the class P is the class of decision problems
solvable by some algorithm within anumber of steps bounded by some xed
polynomial in the length of the input. Turing was notconcerned with
the e ciency of his machines, but rather his concern was whether they
cansimulate arbitrary algorithms given su cient time. However it turns
out Turing machinescan generally simulate more e cient computer models
(for example machines equipped withmany tapes or an unbounded random
access memory) by at most squaring or cubing thecomputation time. Thus
P is a robust class, and has equivalent de nitions over a large
classof computer models. Here we follow standard practice and de ne
the class P in terms ofTuring machines.Formally the elements of the
class P are languages. Let be a nite alphabet (that is, anite nonempty
set) with at least two elements, and letbe the set of nite strings
over .Then a language over is a subset L of. Each Turing machine M has
an associated inputalphabet . For each string w inthere is a
computation associated with M with input w.(The notions of Turing
machine and computation are de ned formally in the appendix.) Wesay
that M accepts w if this computation terminates in the accepting
state. Note that Mfails to accept w either if this computation ends in
the rejecting state, or if the computationfails to terminate. The
language accepted by M, denoted L(M), has associated alphabetand is de
ned byL(M) = fw 2 jM accepts wgWe denote by tM (w) the number of steps
in the computation of M on input w (see theAppendix). If this
computation never halts, then t M (w) = 1. For n 2 N we denote byTM
(n) the worst case run time of M; that isTM (n) = maxft M (w) jw 2
ngwhere n is the set of all strings over of length n. We say that M
runs in polynomial timeif there exists k such that for all n, T M (n)
n k + k. Now we de ne the class P of languagesbyP = fL jL = L(M) for
some Turing machine M which runs in polynomial timeg1
--------------------------------------------------------------------------------
Page 2
The notation NP stands for \nondeterministic polynomial time", since
originally NP wasde ned in terms of nondeterministic machines (that
is, machines that have more than onepossible move from a given con
guration). However now it is customary to give an equivalentde nition
using the notion of a checking relation, which is simply a binary
relation R1 for some nite alphabets and 1. We associate with each such
relation R alanguage LR over [ 1 [f#g de ned byLR = fw#y jR(w; y)
gwhere the symbol # is not in . We say that R is polynomial-time i LR
2P.Now we de ne the class NP of languages by the condition that a
language L over is inNP i there is k 2N and a polynomial-time checking
relation R such that for all w 2 ,w 2L () 9y(jyj jwj k and R(w; y))
where jwj and jyjdenote 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 assumejj 2), since strings
over an alphabet of any xed size can be e ciently coded by stringsover
a binary alphabet. (For jj = 1 the problem is still open, although it
is possible thatP = 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 2 P
then we cande ne the polynomial-time checking relation R[ byR(w; y) ()
w 2Lfor all w; y 2 .Here are two simple examples, using decimal
notation to code natural numbers: The set ofperfect squares is in P
and the set of composite numbers is in NP (and not known to be inP).
For the latter, the associated polynomial time checking relation R is
given byR(a; b) ()1 < b < a and bja(1)In general the decimal notation
for a natural number c is denoted by c.2. History and ImportanceThe
importance of the P vs NP questions stems from the successful theories
of NP-completeness and complexity-based cryptography, as well as the
potentially stunning prac-tical consequences of a constructive proof
of P = NP.The theory of NP-completeness has its roots in computability
theory, which originated inthe work of Turing, Church, G odel, and
others in the 1930’s. The computability precursors2
--------------------------------------------------------------------------------
Page 3
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) i L = L(M)for some Turing machine M. We
say that L is decidable i L = L(M) for some Turingmachine M which
satis es the condition that M halts on all input strings w. There is
anequivalent de nition of c.e. which brings out its analogy with NP,
namely L is c.e. i thereis a computable \checking relation" R(x; y)
such that L = fx j9yR(x; y)g.Using the notation hMi to denote a string
describing a Turing machine M, we de ne theHalting Problem HP as
follows:HP = fhMijM is a Turing machine which halts on input
hMigTuring used a simple diagonal argument to show that HP is not
decidable. On the otherhand, it is not hard to show that HP is c.e.Of
central importance in computability theory is the notion of
reducibility, which Turingde ned roughly as follows: A language L1 is
Turing reducible to a language L 2 i there isan oracle Turing machine
M which accepts L1, where M is allowed to make membershipqueries of
the form x 2 L2? which are correctly answered by an \oracle" for L2.
Later themore restricted notion of many-one reducibility ( m) was
introduced and de ned as follows.De nition 1: Suppose that L i is a
language over i , i = 1; 2. Then L 1m L2 i there is a(total)
computable function f : 1 ! 2 such that x 2L1 ()f(x) 2L2, for all x 2
1.It is easy to see that if L1m L2 and L2 is decidable, then L1 is
decidable. This factprovides an important tool for showing
undecidability; for example if HPm L then L isundecidable.The notion
of NP-complete is based on the following notion from computability
theory:De nition 2: A language L is c.e.-complete i L is c.e., and L0m
L for every c.e. languageL0 .It is easy to show that HP is c.e.-
complete. It turns out that most \natural" undecidablec.e. languages
are in fact c.e.-complete. Since m is transitive, to show that a c.e.
languageL is c.e. complete is su ces to show that HPm 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 the-ory (although earlier von Neumann [vN53]
in 1953 distinguished between polynomial timeand exponential-time
algorithms). Edmonds called polynomial-time algorithms \good algo-
rithms", and linked them to tractable algorithms.It has now become
standard in complexity theory to identify polynomial-time with feasi-
ble, and here we digress to discuss this point. It is of course not
literally true that everypolynomial-time algorithm can be feasibly
executed on small inputs; for example a computerprogram requiring n100
steps could never be executed on an input even as small as n = 10.Here
is a more defensible statement (see [Coo91]):3
--------------------------------------------------------------------------------
Page 4
Feasibility Thesis: A natural problem has a feasible algorithm i it
has a polynomial-timealgorithm.Examples of natural problems that have
both feasible and polynomial-time algorithms abound:Integer
arithmetic, linear algebra, network ow, linear programming, many graph
problems(connectivity, shortest path, minimum spanning tree, bipartite
matching) etc. On the otherhand the deep results of Robertson and
Seymour [RS95] provide a potential source of coun-terexamples to the
thesis: They prove that every minor-closed family of graphs can
berecognized in polynomial time (in fact in time O(n 3)), but the
algorithms supplied by theirmethod have such huge constants that they
are not feasible. However each potential counterexample can be removed
by nding a feasible algorithm for it. For example a feasible recog-
nition algorithm is known for the class of planar graphs, but none is
currently known forthe class of graphs embeddable in R3 with no two
cycles linked. (Both examples are minor-closed families.) Of course
the words \natural" and \feasible"in the thesis above should
beexplained; generally we do not consider a class with a parameter as
natural, such as the setof graphs embeddable on a surface of genus k,
k > 1.We mention two concerns related to the \only if" direction of
the thesis. The rst comesfrom randomized algorithms. We discuss at the
end of section 3 the possibility that a sourceof random bits might be
used to greatly reduce the recognition time required for somelanguage.
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 theidea of superposition of states from
quantum mechanics, and allows a potential exponentialspeed-up of some
computations over Turing machines. For example, Shor [Sho97] has
shownthat some quantum computer algorithm is able to factor integers
in polynomial time, butno polynomial-time integer factoring algorithm
is known for Turing machines. Howeverphysicists have so far been
unable to build a quantum computer that can handle more thana 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[Coo71] introduced a notion of NP-
completeness as a polynomial-time analog of c.e. com-pleteness, except
that the reduction used was a polynomial- time analog of Turing
reducibilityrather than of many-one reducibility. The main results in
[Coo71] are that several naturalproblems, including Satis ability and
3-SAT (de ned below) and subgraph isomorphism areNP-complete. A year
later Karp [Kar72] used these completeness results to show that
20other natural problems are NP-complete, thus forcefully
demonstrating the importance ofthe subject. Karp also introduced the
now standard notation P and NP and rede ned NP-completeness using the
polynomial-time analog of many-one reducibility, a de nition whichhas
become standard. Meanwhile Levin [Lev73] independently of Cook and
Karp de nedthe notion of \universal search problem", similar to NP-
complete problem, and gave sixexamples, including Satis ability.The
standard de nitions concerning NP-completeness are close analogs of De
nitions 1 and2 above.4
--------------------------------------------------------------------------------
Page 5
De nition 3: Suppose that L i is a language over i , i = 1; 2. Then L
1p L2 (L 1 isp-reducible to L 2) i there is a polynomial-time
computable function f :1 ! 2 such thatx 2L1 ()f(x) 2L2, for all x 2
1.De nition 4: A language L isNP-complete i L is in NP, and L0p L for
every languageL0in NP.The following proposition is easy to prove: Part
(b) uses the transitivity ofp, and part (c)follows from part
(a).Proposition 1: (a) If L 1p L2 and L2 2P then L1 2P.(b) If L 1 is
NP-complete, L 2 2NP, and L1p L2 then L 2 is NP-complete.(c) If L is
NP-complete and L 2P, 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 forshowing new problems are NP-complete, and part (c)
explains why it is probably a wasteof 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 corresponding lan-guage is
understood to mean the set of strings coding YES instances to the
decision problemusing standard coding methods. Thus the problem Satis
ability is: Given a propositionalformula F, determine whether F is
satis able. To show that this is in NP we de ne thepolynomial-time
checking relation R(x; y), which holds i x codes a propositional
formula Fand y codes a truth assignment to the variables of F which
makes F true. This problem wasshown to be NP-complete in [Coo71]
essentially by showing that for each polynomial-timeTuring machine M
which recognizes a checking relation R(x; y) for an NP language L,
thereis a polynomial-time algorithm which takes as input a string x
and produces a propositionalformula F x (describing the computation of
M on input (x;y), with variables representingthe unknown string y)
such that F x is satis able i M accepts the input (x;y) for some ywith
jyj jxj O(1) .An important special case of Satis ability is 3-SAT,
which was also shown to be NP-completein [Coo71]. Instances of 3-SAT
are restricted to formulas in conjunctive normal form withthree
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 satis es the formula, where (P) =(Q) = True and (R) = (S) =
False.Many hundreds of NP-complete problems have been identi ed,
including SubsetSum (givena set of positive integers presented in
decimal notation, and a target T, is there a subsetsumming 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 withthree colors with distinct colors for
adjacent vertices?). These problems give rise to many5
--------------------------------------------------------------------------------
Page 6
scheduling and routing problems with industrial importance. The book
[GJ79] provides anexcellent 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 astring x, nd
a string y satisfying the checking relation R(x; y) for the problem
(or determinethat x is a NO instance to the problem). Such a y is said
to be a certi cate for x. In thecase of an NP-complete problem it is
easy to see that the search problem can be e cientlyreduced to the
corresponding decision problem. In fact if P = NP then the associated
searchproblem for every NP problem has a polynomial-time algorithm.
For example, an algorithmfor the decision problem Satis ability can be
used to nd a truth assignment satisfying agiven satis able formula F
by, for each variable P in F in turn, setting P to True in F orFalse
in F, which ever case keeps F satis able.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
oftautologies (propositional formulas true under all assignments) is
the standard example of acoNP-complete language. The conjecture NP 6=
coNP is equivalent to the assertion thatno formal proof system
(suitably de ned) for tautologies has short (polynomial-bounded)proofs
for all tautologies [CR79]. This fact has motivated the development of
a rich theoryof proportional proof complexity [Kra95], one of whose
goals is to prove superpolynomiallower 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 rst section,
with checkingrelation (1). Here it is conjectured that there is no
polynomial-time Turing reduction fromthe search problem (integer
factoring) to the decision problem. Speci cally, Miller [Mil76]showed
how to determine in polynomial time whether a given number is
composite, assumingthe Extended Riemann Hypothesis, but a polynomial-
time integer factoring algorithm isthought unlikely to exist. In fact
an e cient factoring algorithm would break the RSApublic key
encryption scheme [ARS78] commonly used to allow (presumably) secure
nancialtransactions over the internet.The complement of the set of
composite numbers (essentially the set of primes) was provedto be in
NP by an interesting argument due to Pratt [Pra75], and hence is
unlikely to beNP-complete.There is an NP decision problem with
complexity equivalent to that of integer factoring,namelyLfact = fha;
bij9d(1 < d < a and djb)gGiven an integer b > 1, the smallest prime
divisor of b can be found with about log2 b queriesto L fact , using
binary search. Using Pratt’s theorem, it is easy to see that the
complementof Lfact is also in NP: a certi cate showing ha; bi is a non-
instance of Lfact could be thecomplete prime decomposition of b,
together with Pratt certi cates proving that each of theprime factors
is indeed prime. Thus it is considered unlikely that L fact is NP-
complete.Computational complexity theory plays an important role in
modern cryptography [Gol00].6
--------------------------------------------------------------------------------
Page 7
The security of the internet, including most nancial transactions,
depend on complexity-theoretic assumptions such as the di culty of
integer factoring or of breaking DES (the DataEncryption Standard). If
P= NP these assumptions are all false. Speci cally, an
algorithmsolving 3-SAT in n2 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 practi-cal
consequences of a more positive nature, and not just because of the e
cient solutionsto the many NP-hard problems important to industry. For
example, it would transformmathematics by allowing a computer to nd a
formal proof of any theorem which has aproof of reasonable length,
since formal proofs can easily be recognized in polynomial
time.Example theorems may well include all of the CMI prize problems.
Although the formalproofs may not be initially intelligible to humans,
the problem of nding intelligible proofswould be reduced to that of
nding a recognition algorithm for intelligible proofs. Similar re-
marks apply to diverse creative human endeavors, such as designing
airplane wings, creatingphysical theories, or even composing music.
The question in each case is to what extent ane cient algorithm for
recognizing a good result can be found. This is a fundamental
problemin arti cial intelligence, and one whose solution itself would
be aided by the NP-solver byallowing easy testing of recognition
theories.Even if P 6= 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 impossibleand bring about most
of the bene ts of a world in which P = NP. This also motivatesLevin’s
theory [Lev86, Imp95] of average case completeness, in which the P =
NP questionis replaced by the question of whether every NP problem
with any reasonable probabilitydistribution 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 problems for thenext century.
However Smale is interested not just in the classical version of the
question,but also a version expressed in terms of the eld of complex
numbers. Here Turing machinesmust be replaced by a machine model that
is capable of doing exact arithmetic and zerotests on arbitrary
complex numbers. The P vs NP question is replaced by a questionrelated
to Hilbert’s Nullstellensatz: Is there a polynomial-time algorithm
which, given a setof 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 intriguingresult that
the Mandelbrot set is undecidable.The books by Papadimitriou [Pap94]
and Sipser [Sip97] provide good introductions to main-stream
complexity theory.3. The Conjecture and Attempts to Prove itMost
complexity theorists believe that P6= NP. Perhaps this can be partly
explained bythe potentially stunning consequences of P = NP mentioned
above, but there are betterreasons. We explain these by considering
the two possibilities in turn: P= NP and P 6=NP.7
--------------------------------------------------------------------------------
Page 8
Suppose rst that P = NP and consider how one might prove it. The
obvious way is toexhibit 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 isa standard
toolkit available [CLR90] for devising polynomial-time algorithms,
including thegreedy method, dynamic programming, reduction to linear
programming, etc. These are thesubjects of a course on algorithms,
typical in undergraduate computer science curriculums.Because of their
importance in industry, a vast number of programmers and engineers
haveattempted to nd e cient algorithms for NP-complete problems over
the past 30 years,without success. There is similar strong motivation
for breaking the cryptographic schemeswhich assume P 6= NP for their
security.Of course it is possible that some nonconstructive argument,
such as the Roberton/Seymourproofs mentioned earlier in conjunction
with the Feasibility Thesis, could show that P = NPwithout yielding
any feasible algorithm for the standard NP-complete problems.
Howeverat present the best proven upper bound on an algorithm for
solving 3-SAT is approximately1:5n, where n is the number of variables
in the input formula.Suppose on the other hand that P 6= NP, and
consider how one might prove it. There aretwo general methods that
have been tried: diagonalization/reduction and Boolean circuitlower
bounds.The method of diaonalization with reduction has been used very
successfully in computabilitytheory to prove a host of problems
undecidable, beginning with the Halting Problem. It hasalso been used
successfully in complexity theory to prove super-exponential lower
boundsfor very hard decidable problems. For example, Presburger
arithmetic, the rst-order theoryof integers under addition, is a
decidable theory for which Fischer and Rabin [FR74] provedthat any
Turing machine deciding the theory must use at least 22cnsteps in the
worst case,for some c > 0. In general, lower bounds using
diagonalization and reduction relativize; thatis they continue to
apply in a setting in which both the problem instance and the
solvingTuring 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, suggestingthat diagonalization/
reduction cannot be used to separate these two classes. (There
arenonrelativizing results in complexity theory, as will be mentioned
below.) It is interesting tonote that relative to a generic oracle, P
6= NP [BI87, SCY97].A Boolean circuit is a nite acyclic graph in which
each non-input node, or gate, is labelledwith a Boolean connective;
typically from fAN D; OR; N OTg. The input nodes are labeledwith
variables x 1; :::; x n, and for each assignment of 0 or 1 to each
variable the circuit com-putes a bit value at each gate, including the
output gate, in the obvious way. It is not hardto see that if L is a
language over f0; 1g that is in P, then there is a polynomial-size
familyof Boolean circuits hBni 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 Bn, then the output bit of B n is 1 i w 2 L. Inthis case we say
that hBni computes L.Thus to prove P 6= NP it su ces to prove a super-
polynomial lower bound on the size of any8
--------------------------------------------------------------------------------
Page 9
family of Boolean circuits solving some speci c NP-complete problem,
such as 3-SAT. Backin 1949 Shannon [Sha49] proved that for almost all
Boolean functions f : f0; 1gn ! f0; 1g,any Boolean circuit computing f
requires at least 2 n=n gates. Unfortunately his countingargument
gives no clue as to how to prove lower bounds for problems in NP.
Exponentiallower bounds for NP problems have been proved for
restricted circuit models, includingmonotone circuits [Raz85, AB87]
and bounded depth circuits with unbounded fan-in gates[Has89, Smo87]
(see [BS90]). However all attempts to nd even super-linear lower
boundsfor unrestricted Boolean circuits for \explicitly given" Boolean
functions have met withtotal 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 classi edas \Natural
Proofs", and Natural Proofs for general circuit lower bounds are
doomed tofailure, assuming a certain complexity-theoretic conjecture
asserting that strong pseudo-random number generators exist. Since
such generators have been constructed assuming thehardness of integer
factorization, we can infer the surprising result that a Natural Proof
fora general circuit lower bound would give rise to a more e cient
factoring algorithm than iscurrently known.The failure of complexity
theory to prove interesting lower bounds on a general model
ofcomputation is much more pervasive than the failure to prove P 6=
NP. It is consistentwith present knowledge that not only could Satis
ability have a polynomial-time algorithm,it could have a linear time
algorithm on a multitape Turing machine. The same appliesfor all 21
problems mentioned in Karp’s original paper [Kar72]. There are
complexity classseparations which we know exist but cannnot prove. For
example, consider the sequence ofcomplexity class inclusionsLOGSPACE P
NP PSPACEA simple diagonal arugment shows that the rst is a proper
subset of the last, but we cannotprove any particular adjacent
inclusion is proper.As another example, let LINEAR-SIZE be the class
of languages over f0; 1g which canbe computed by a family hBni of
Boolean circuits of size O(n). It is not known whethereither P or NP
is a subset of LINEAR-SIZE, although Kannan [Kan82] proved that
thereare 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 haveProposition 2: If P LINEAR-SIZE, then P 6=
NP.This proposition could be interpreted as a method of proving P 6=
NP, but a more usualbelief is that the hypothesis is false.A
fundamental question in complexity theory is whether a source of
random bits can beused to substantially speed up the recognition of
some languages, provided one is willing toaccept a small probability
of error. The class BPP consists of all languages L which canbe
recognized by a randomized polynomial-time algorithm, with at most an
exponentiallysmall error probability on every input. Of course P BPP,
but it is not known whetherthe inclusion is proper. The set of prime
numbers is in BPP [SS77], but it is not known9
--------------------------------------------------------------------------------
Page 10
to be in P. A reason for thinking that BPP = P is that randomized
algorithms are oftensuccessfully 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 classof languages L such that L = L(M) for some
Turing machine M with T M (n) = O(2 cn) forsome c > 0. Let A be the
assertion that some language in E requires exponential
circuitcomplexity. That isAssertion A: There is L 2 E and > 0 such
that for every circuit family hB ni computingL and for all su ciently
large n, B n has at least 2n gates.Proposition 3: If A then BPP = P.
If not A then P 6= NP.The rst implication is a lovely theorem by
Impagliazzo and Wigderson [IW97] and thesecond is an intriguing
observation by V. Kabanets which strengthens Proposition 2. In
factKabanets concludes P 6= NP from a weaker assumption than not A;
namely that everylanguage in E can be computed by a Boolean circuit
family hBni such that for at leastone n, Bn has fewer gates than the
maximum needed to compute any Boolean functionf : f0; 1gn !f0; 1g. 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 constructionwill be needed if one is to prove P 6=
NP by giving small circuits for languages in E. Howevernonrelativizing
constructions have been used successfully before, for example in
showing IP(Interactive Polynomial time) contains all of PSPSACE
[Sha92]. In this and other suchconstructions a key technique is to
represent Boolean functions by multivariate polynomialsover nite
elds.Appendix: De nition of Turing machineA Turing machine M consists
of a nite state control (i.e. a nite program) attached toread/write
head moving on an in nite tape. The tape is divided into squares, each
capableof storing one symbol from a nite alphabet which includes the
blank symbol b. Eachmachine M has a speci ed input alphabet , which is
a subset of , not including the blanksymbol b. At each step in a
computation M is in some state q in a speci ed nite set Q ofpossible
states. Initially a nite input string over is written on adjacent
squares of thetape, all other squares are blank (contain b), the head
scans the left-most symbol of theinput string, and M is in the initial
state q 0. At each step M is in some state q and the headis scanning a
tape square containing some tape symbol s, and the action performed
dependson the pair (q;s) and is speci ed by the machine’s transition
function (or program) . Theaction consists of printing a symbol on the
scanned square, moving the head left or right onesquare, and assuming
a new state.Formally a Turing machine M is a tuple h; ; Q; i where ; ;
Q are nite nonempty sets10
--------------------------------------------------------------------------------
Page 11
withand b 2 . The state set Q contains three special states
q0;qaccept;qreject .The transition function satis es: (Q fq
accept;qreject g)!Qf 1; 1gIf (q; s) = (q 0 ;s0 ;h) the interpretation
is that if M is in state q scanning the symbol s thenq0 is the new
state, s0is the symbol printed, and the tape head moves left or right
one squaredepending on whether h is -1 or 1.We assume that the sets Q
and are disjoint.A con guration of M is a string xqy with x;y 2, y not
the empty string, and q 2Q.The interpretation of the con guration xqy
is that M is in state q with xy on its tape, withits head scanning the
left-most symbol of y.If C and C 0are con gurations, then CM!C 0if C =
xqsy and (q;s) = (q 0 ;s0 ;h) and one ofthe following holds:C0 = xs 0
q0 y and h = 1 and y is nonempty.C0 = xs 0 q0 b and h = 1 and y is
empty.C0 = x 0 q0 as0 y and h = 1 and x = x 0 a for some a 2 .C0 = q 0
bs0 y and h = 1 and x is empty.A con guration xqy is halting if q 2fq
accept;qreject g. Note that for each non-halting con gu-ration C there
is a unique con guration C 0such that CM!C 0 .The computation of M on
input w 2is the unique sequence C0;C1;::: of con gurationssuch that C0
= q0w (or C0 = q0b if w is empty) and CiM! C i+1 for each i with C i+1
in thecomputation, and either the sequence is in nite or it ends in a
halting con guration. If thecomputation is nite, then the number of
steps is one less than the number of con gurations;otherwise the
number of steps is in nite. We say that M accepts w i the computation
isnite and the nal con guration contains the state q
accept.AcknowledgmentsMy thanks to Avi Wigderson and Hugh Woodin for
many helpful suggestions for improvingan earlier version of this
paper.References[AB87] N. Alon and R. B. Boppana. The monotone circuit
complexity of boolean func-tions. Combinatorica, 7(1):1{22, 1987.
[ARS78] L. Adleman, R. L. Rivest, and A. Shamir. A method for
obtaining digital signatureand public-key cryptosystems. Communication
of the ACM, 21(2), 1978.11
--------------------------------------------------------------------------------
Page 12
[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 Symposium on Foundations ofComputer
Science, pages 118{126, Los Angeles, CA, October 1987. IEEE Com-puter
Society Press.[BS90]R. B. Boppana and M. Sipser. The complexity of
nite functions. In J. VanLeeuwen, editor, Handbook of Theoretical
Computer Science, Volume A: Algo-rithms and Complexity, pages 759{804.
Elsevier and The MIT Press, 1990.[CLR90] T. Cormen, C. Leiserson, and
R. Rivest. Introduction to Algorithms. McGrawHill, New York, 1990.
[Cob64] A. Cobham. The intrinsic computational di culty of functions.
In Yehoshua Bar-Hillel, editor, Proceedings of the 1964 International
Congress for Logic, Method-ology, and Philosophy of Science, pages 24
{30. Elsevier/North-Holland, 1964.[Coo71] Stephen Cook. The complexity
of theorem-proving procedures. In ConferenceRecord of Third Annual ACM
Symposium on Theory of Computing, pages 151{158, 1971.[Coo91] Stephen
Cook. Computational complexity of higher type functions. In Ichiro Sa-
take, editor, Proceedings of the International Congress of
Mathematicians, Kyoto,Japan, pages 55{69. Springer{Verlag, 1991.[CR79]
S. Cook and R. Reckhow. The relative e ciency 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 Presburgerarithmetic. In R. M. Karp,
editor, Complexity of Computation, volume 7, pages27{41. American
Mathematical Society, Providence, RI, 1974.[GJ79]M. R. Garey and D. S.
Johnson. Computers and Intractibility, a Guide to theTheory of NP-
Completeness. W.H. Freeman and Co., San Francisco, 1979.[Gol00] Oded
Goldreich. The Foundations of Cryptography{Volume 1. Cambridge Uni-
versity Press, 2000.[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.12
--------------------------------------------------------------------------------
Page 13
[Imp95] R. Impagliazzo. A personal view of average-case complexity. In
10th IEEE AnnualConference on Structure in Complexity Theory, pages 134
{147, 1995.[IW97]R. Impagliazzo and A. Wigderson. P = BPP if E
requires exponential circuits:Derandomizing the XOR lemma. In STOC:
ACM Symposium on Theory of Com-puting (STOC), 1997.[Kan82] Ravi
Kannan. Circuit-size lower bounds and non-reducibility to sparse sets.
In-formation and Control, 55:40{56, 1982.[Kar72] Richard M. Karp.
Reducibility among combinatorial problems. In R. E. Miller andJ. W.
Thatcher, editors, Complexity of Computer Computations, pages 85
{103,New York, 1972. Plenum Press.[Kra95] J. Krajicek. Bounded
Arithmetic, Propositional Logic, and Complexity Theory.Cambridge, 1995.
[Lev73] L. Levin. Universal search problems (in russian)". Problemy
Peredachi Infor-matsii, 9(3):265{266, 1973. English translation in
Trakhtenbrot, B. A.: A surveyof Russian approaches to Perebor (brute-
force search) algorithms. Annals of theHistory of Computing, 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. SystemSci, 13:300{317,
1976.[Pap94] Christos Papadimitriou. Computational Complexity. Addison
{Wesley, 1994.[Pra75] V. R. Pratt. Every prime has a succinct certi
cate. SIAM Journal on Computing,4(3):214{220, 1975.[Raz85] Alexander
A. Razborov. Lower bounds on the monotone complexity of someboolean
functions. Soviet Math. Dokl., 31:354{357, 1985.[RR97] Alexander A.
Razborov and Steven Rudich. Natural proofs. Journal of Computerand
System Sciences, 55(1):24{35, August 1997.[RS95]N. Robertson and P. D.
Seymour. Graph minors i{xiii. Journal of CombinatorialTheory B, 1983
{1995.[SCY97] R. Impagliazzo S. Cook and T. Yamakami. A tight
relationship between genericoracles 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 Tech-nical Journal, 28:59{98, 1949.13
--------------------------------------------------------------------------------
Page 14
[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 log-arithms on a quantum computer. SIAM J. Computing, 26:1484
{1509, 1997.[Sip97]Michael Sipser. Introduction to the Theory of
Computation. PWS, 1997.[Sma98] Steve Smale. Mathematical problems for
the next century. MATHINT: TheMathematical Intelligencer, 20, 1998.
[Smo87] R. Smolensky. Algebraic methods in the theory of lower bounds
for boolean circuitcomplexity. In ACM Symposium on Theory of Computing
(STOC), volume 19,pages 77{82, 1987.[SS77]R. Solovay and V. Strassen.
A fast Monte-Carlo test for primality. SIAM Journalon Computing, 6(1):
84{85, March 1977.[Tur36] Alan Turing. On computable numbers with an
application to the entscheid-nungsproblem. Proc. London Math. Soc.
ser. 2, 42:230{265, 1936-7.[vN53]J. von Neumann. A certain zero-sum
two-person game equivalent to the optimalassignment problem. In H. W.
Kahn and A. W. Tucker, editors, Contributions tothe Theory of Games
II. Princeton Univ. Press, 1953.14
.
- References:
- Re: an oracle paradox
- From: scarlett
- Re: an oracle paradox
- Prev by Date: Re: an oracle paradox
- Next by Date: Re: at most countable
- Previous by thread: Re: an oracle paradox
- Index(es):
Relevant Pages
|
