714:: whereas an NP problem asks "Are there any solutions?", the corresponding #P problem asks "How many solutions are there?". Clearly, a #P problem must be at least as hard as the corresponding NP problem, since a count of solutions immediately tells if at least one solution exists, if the count is greater than zero. Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear-time) P problems. For these problems, it is very easy to tell whether solutions exist, but thought to be very hard to tell how many. Many of these problems are
340:? It is straightforward to verify "yes" instances of this generalized Sudoku problem given a candidate solution. However, it is not known whether there is a polynomial-time algorithm that can correctly answer "yes" or "no" to all instances of this problem. Therefore, generalized Sudoku is in NP (quickly verifiable), but may or may not be in P (quickly solvable). (It is necessary to consider a generalized version of Sudoku, as any fixed size Sudoku has only a finite number of possible grids. In this case the problem is in P, as the answer can be found by table lookup.)
1723:, correspond to all of second-order logic. Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?". The word "existential" can even be dropped from the previous characterization, since P = NP if and only if P = PH (as the former would establish that NP = co-NP, which in turn implies that NP = PH).
476:
990:
1486:
1564:(which can answer a fixed set of questions in constant time, such as an oracle that solves any traveling salesman problem in 1 step), and the running time of the oracle is not counted against the running time of the algorithm. Most proofs (especially classical ones) apply uniformly in a world with oracles regardless of what the oracle does. These proofs are called
1704:. Recursive functions can be defined with this and the order relation. As long as the signature contains at least one predicate or function in addition to the distinguished order relation, so that the amount of space taken to store such finite structures is actually polynomial in the number of elements in the structure, this precisely characterizes P.
367:, speculating that cracking a sufficiently complex code would require time exponential in the length of the key. If proved (and Nash was suitably skeptical), this would imply what is now called P ≠ NP, since a proposed key can be verified in polynomial time. Another mention of the underlying problem occurred in a 1956 letter written by
1668:(cannot be proved or disproved within them). An independence result could imply that either P ≠ NP and this is unprovable in (e.g.) ZFC, or that P = NP but it is unprovable in ZFC that any polynomial-time algorithms are correct. However, if the problem is undecidable even with much weaker assumptions extending the
707:. They cannot be completely solved by any algorithm, in the sense that for any particular algorithm there is at least one input for which that algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all.
1519:
and generating hard instances of problems outside P is easy, with three intermediate possibilities reflecting different possible distributions of difficulty over instances of NP-hard problems. The "world" where P ≠ NP but all problems in NP are tractable in the average case is called "Heuristica" in the paper. A
1672:
for integer arithmetic, then nearly polynomial-time algorithms exist for all NP problems. Therefore, assuming (as most complexity theorists do) some NP problems don't have efficient algorithms, proofs of independence with those techniques are impossible. This also implies proving independence from PA
1601:
exist, P and NP are indistinguishable to natural proof methods. Although the existence of one-way functions is unproven, most mathematicians believe that they do, and a proof of their existence would be a much stronger statement than P ≠ NP. Thus it is unlikely that natural proofs alone can
1193:
as "Does P = NP?" According to polls, most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems
192:
An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be
557:
The first natural problem proven to be NP-complete was the
Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However,
466:
has conducted three polls of researchers concerning this and related questions. Confidence that P ≠ NP has been increasing – in 2019, 88% believed P ≠ NP, as opposed to 83% in 2012 and 61% in 2002. When restricted to experts, the 2019 answers became 99% believed P ≠ NP.
1518:
has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question. These range from "Algorithmica", where P = NP and problems like SAT can be solved efficiently in all instances, to "Cryptomania", where P ≠ NP
1731:
No known algorithm for a NP-complete problem runs in polynomial time. However, there are algorithms known for NP-complete problems that if P = NP, the algorithm runs in polynomial time on accepting instances (although with enormous constants, making the algorithm impractical). However,
1531:
Although the P = NP problem itself remains open despite a million-dollar prize and a huge amount of dedicated research, efforts to solve the problem have led to several new techniques. In particular, some of the most fruitful research related to the P = NP problem has been in
1506:
A proof of P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would represent a great advance in computational complexity theory and guide future research. It would demonstrate that many common problems cannot be solved efficiently, so that the
5252:
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and
1401:
These changes could be insignificant compared to the revolution that efficiently solving NP-complete problems would cause in mathematics itself. Gödel, in his early thoughts on computational complexity, noted that a mechanical method that could solve any problem would revolutionize mathematics:
1261:
Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the
3171:
compiled a list of 116 purported proofs from 1986 to 2016, of which 61 were proofs of P = NP, 49 were proofs of P ≠ NP, and 6 proved other results, e.g. that the problem is undecidable. Some attempts at resolving P versus NP have received brief media attention, though these
1320:
might show a solution exists without specifying either an algorithm to obtain it or a specific bound. Even if the proof is constructive, showing an explicit bounding polynomial and algorithmic details, if the polynomial is not very low-order the algorithm might not be sufficiently efficient in
3300:
can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as
500:
To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are problems that any other NP problem is reducible to in polynomial time and whose solution is still verifiable in polynomial time. That is, any NP problem can be transformed into any
571:
into triangles, which could then be used to find solutions for the special case of SAT known as 3-SAT, which then provides a solution for general
Boolean satisfiability. So a polynomial-time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of
527:
problem in NP can be transformed mechanically into a
Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many NP-complete problems. If any NP-complete problem is in P, then it would follow that P = NP. However, many important problems are
1308:
A proof that P = NP could have stunning practical consequences if the proof leads to efficient methods for solving some of the important problems in NP. The potential consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields.
960:
1239:
The main argument in favor of P ≠ NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. The resolution of
2912:
759:. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete. If graph isomorphism is NP-complete, the
1202:, among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP =
1371:, and is used to authenticate software updates. For these applications, finding a pre-image that hashes to a given value must be difficult, ideally taking exponential time. If P = NP, then this can take polynomial time, through reduction to SAT.
1480:
given bits, and it's really hard to believe that all of those algorithms fail. My main point, however, is that I don't believe that the equality P = NP will turn out to be helpful even if it is proved, because such a proof will almost surely be
1446:... it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the
2806:
1931:
467:
These polls do not imply whether P = NP, Gasarch himself stated: "This does not bring us any closer to solving P=?NP or to knowing when it will be solved, but it attempts to be an objective report on the subjective opinion of this era."
572:
satisfiability, which in turn can be used to solve any other NP-problem in polynomial time. Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".
1791:
FOR K = 1...∞ FOR M = 1...K Run program number M for K steps with input S IF the program outputs a list of distinct integers AND the integers are all in S AND the integers sum to 0 THEN OUTPUT "yes" and HALT
1656:
These barriers are another reason why NP-complete problems are useful: if a polynomial-time algorithm can be demonstrated for an NP-complete problem, this would solve the P = NP problem in a way not excluded by the above results.
1572:
showed that P = NP with respect to some oracles, while P ≠ NP for other oracles. As relativizing proofs can only prove statements that are true for all possible oracles, these techniques cannot resolve P = NP.
1321:
practice. In this case the initial proof would be mainly of interest to theoreticians, but the knowledge that polynomial time solutions are possible would surely spur research into better (and possibly practical) methods to achieve them.
1217:
If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps", no fundamental gap between solving a problem and recognizing the solution once it's
2291:
763:
collapses to its second level. Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to
562:
provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete
1795:
This is a polynomial-time algorithm accepting an NP-complete language only if P = NP. "Accepting" means it gives "yes" answers in polynomial time, but is allowed to run forever when the answer is "no" (also known as a
1141:
On the other hand, even if a problem is shown to be NP-complete, and even if P ≠ NP, there may still be effective approaches to the problem in practice. There are algorithms for many NP-complete problems, such as the
1124:
1234:
On the other hand, some researchers believe that there is overconfidence in believing P ≠ NP and that researchers should explore proofs of P = NP as well. For example, in 2002 these statements were made:
1299:
One of the reasons the problem attracts so much attention is the consequences of the possible answers. Either direction of resolution would advance theory enormously, and perhaps have huge practical consequences as well.
507:
problems are those at least as hard as NP problems; i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP; i.e., they need not have solutions verifiable in polynomial time.
407:
dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).
813:
1597:. At the time, all previously known circuit lower bounds were natural, and circuit complexity was considered a very promising approach for resolving P = NP. However, Razborov and Rudich showed that if
2232:
2812:
2455:
2005:
622:
to it. A number of problems are known to be EXPTIME-complete. Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. In fact, by the
3124:
1507:
attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.
359:
Although the P versus NP problem was formally defined in 1971, there were previous inklings of the problems involved, the difficulty of proof, and the potential consequences. In 1955, mathematician
2365:
3578:
1514:
of hard problems in NP. For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable.
2603:
4887:
4631:
2929:
is a member of COMPOSITE. It can be shown that COMPOSITE ∈ NP by verifying that it satisfies the above definition (if we identify natural numbers with their binary representations).
1018:
First, it can be false in practice. A theoretical polynomial algorithm may have extremely large constant factors or exponents, rendering it impractical. For example, the problem of
2706:
2110:
179:". For some questions, there is no known way to find an answer quickly, but if provided with an answer, it can be verified quickly. The class of questions where an answer can be
2635:
1454:
Research mathematicians spend their careers trying to prove theorems, and some proofs have taken decades or even centuries to find after problems have been stated—for instance,
3055:
3017:
2529:
1873:
1472:
that's finite but incredibly large—like say the number 10↑↑↑↑3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do
285:
2407:
3380:
1430:, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number
1316:
lead to practical algorithms for NP-complete problems. The formulation of the problem does not require that the bounding polynomial be small or even specifically known. A
4708:
2375:
5208:
This problem concerns the issue of whether questions that are easy to verify (a class of queries called NP) also have solutions that are easy to find (a class called P).
693:
311:
3344:
4427:
for a reduction of factoring to SAT. A 512-bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.
2052:
338:
3233:
problem, where R is analog of class P, and RE is analog class NP. These classes are not equal, because undecidable but verifiable problems do exist, for example,
4153:
Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of
Computer Science, University of Copenhagen, Copenhagen, Denmark
1213:
It is also intuitively argued that the existence of problems that are hard to solve but for which the solutions are easy to verify matches real-world experience.
554:
that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.
1646:
and the
Boolean circuits to an algebraic problem. As mentioned previously, it has been proven that this method is not viable to solve P = NP and other
586:
Although it is unknown whether P = NP, problems outside of P are known. Just as the class P is defined in terms of polynomial running time, the class
1382:
There are also enormous benefits that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in
736:
showed that if P ≠ NP, then there exist problems in NP that are neither in P nor NP-complete. Such problems are called NP-intermediate problems. The
718:, and hence among the hardest problems in #P, since a polynomial time solution to any of them would allow a polynomial time solution to all other #P problems.
2238:
531:
From the definition alone it is unintuitive that NP-complete problems exist; however, a trivial NP-complete problem can be formulated as follows: given a
4474:
in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses. A 3DES problem instance would be about 3 times this size.
1732:
these algorithms do not qualify as polynomial time because their running time on rejecting instances are not polynomial. The following algorithm, due to
117:
1065:
5190:"The Top Unsolved Questions in Mathematics Remain Mostly Mysterious Just one of the seven Millennium Prize Problems named 21 years ago has been solved"
1867:
and we place it in the class P. Formally, P is the set of languages that can be decided by a deterministic polynomial-time Turing machine. Meaning,
1458:
took over three centuries to prove. A method guaranteed to find a proof if a "reasonable" size proof exists, would essentially end this struggle.
5905:
5189:
4568:
1394:. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in
5930:
4943:
3571:
1283:
When one substitutes "linear time on a multitape Turing machine" for "polynomial time" in the definitions of P and NP, one obtains the classes
955:{\displaystyle O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)}
748:
are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P or to be NP-complete.
2308:. Formally, NP is the set of languages with a finite alphabet and verifier that runs in polynomial time. The following defines a "verifier":
135:
40:
4484:
De, Debapratim; Kumarasubramanian, Abishek; Venkatesan, Ramarathnam (2007). "Inversion attacks on secure hash functions using SAT solvers".
3749:
3406:
1803:
This algorithm is enormously impractical, even if P = NP. If the shortest program that can solve SUBSET-SUM in polynomial time is
787:. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the
5503:
4884:
3951:
4660:
3546:
2298:
NP can be defined similarly using nondeterministic Turing machines (the traditional way). However, a modern approach uses the concept of
411:
In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is
387:, and pointed out one of the most important consequences—that if so, then the discovery of mathematical proofs could be automated.
1532:
showing that existing proof techniques are insufficient for answering the question, suggesting novel technical approaches are required.
5253:
requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem...
3167:
While the P versus NP problem is generally considered unsolved, many amateur and some professional researchers have claimed solutions.
2907:{\displaystyle R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ and }}y{\text{ divides }}x\right\}.}
1426:), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the
799:
and co-UP). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP = co-NP). The most
490:, NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)
70:
2129:
5935:
2412:
1942:
1630:, was also insufficient to resolve P = NP. Arithmetization converts the operations of an algorithm to algebraic and basic
710:
It is also possible to consider questions other than decision problems. One such class, consisting of counting problems, is called
550:; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine
4294:
3267:
1173:
Finally, there are types of computations which do not conform to the Turing machine model on which P and NP are defined, such as
501:
NP-complete problem. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.
110:
4712:
3722:
3245:
3186:, by director Timothy Lanzone, is the story of four mathematicians hired by the US government to solve the P versus NP problem.
1329:
5090:
4247:. Oxford Lecture Series in Mathematics and its Applications. Vol. 4. New York: Oxford University Press. pp. 103–144.
1398:, are also NP-complete; making these problems efficiently solvable could considerably advance life sciences and biotechnology.
5925:
5423:
5358:
5284:
5156:
4603:
4420:
3277:
91:
3686:
3212:
2324:
1493: NP. The existence of problems within NP but outside both P and NP-complete, under that assumption, was established by
1328:, which relies on certain problems being difficult. A constructive and efficient solution to an NP-complete problem such as
4837:
60:
4856:
783:
of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than
5455:
4809:
3071:
417:(given the computer's present state and any inputs, there is only one possible action that the computer might take) and
5920:
5915:
619:
103:
5865:
5316:
5116:
4367:
3521:
3481:
1661:
1199:
1009:
All of the above discussion has assumed that P means "easy" and "not in P" means "difficult", an assumption known as
627:, they cannot be solved in significantly less than exponential time. Examples include finding a perfect strategy for
1464:
has stated that he has come to believe that P = NP, but is reserved about the impact of a possible proof:
5496:
4590:
1447:
447:
5075:
4173:
3898:
3297:
3182:
1536:
400:
3310:
Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of
1610:
After the Baker–Gill–Solovay result, new non-relativizing proof techniques were successfully used to prove that
3202:", the equation P = NP is seen shortly after Homer accidentally stumbles into the "third dimension".
2539:
1376:
1151:
512:
142:. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
1681:
The P = NP problem can be restated as certain classes of logical statements, as a result of work in
4488:. International Conference on Theory and Applications of Satisfiability Testing. Springer. pp. 377–382.
2801:{\displaystyle \mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ for integers }}p,q>1\right\}}
1340:, a foundation for many modern security applications such as secure financial transactions over the Internet.
776:
745:
4141:
1434:
so large that when the machine does not deliver a result, it makes no sense to think more about the problem.
5303:
3501:
1395:
1347:
1195:
1127:
752:
595:
451:
139:
4117:
Proceedings of the
International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures
2057:
1926:{\displaystyle \mathbf {P} =\{L:L=L(M){\text{ for some deterministic polynomial-time Turing machine }}M\}}
5489:
1391:
1357:
17:
3215:
Sherlock and Watson investigate the murders of mathematicians who were attempting to solve P versus NP.
2608:
5900:
5881:
5688:
5350:
5270:
4289:
4164:
3596:
3234:
2472:
1147:
804:
741:
250:
232:
5448:
5220:
5034:
4561:
2379:
977:, runs in polynomial time, although this does not indicate where the problem lies with respect to non-
5376:
5308:
4728:
4709:"Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds""
1829:
978:
760:
737:
413:
228:
51:
4908:
4528:
4216:
3665:
3349:
1673:
or ZFC with current techniques is no easier than proving all NP problems have efficient algorithms.
1558:
Imagine a world where every algorithm is allowed to make queries to some fixed subroutine called an
1535:
As additional evidence for the difficulty of the problem, essentially all known proof techniques in
5870:
5390:
4452:
3426:
2300:
1712:
1455:
1241:
364:
3022:
2984:
2536:
699:. Hence, the problem is known to need more than exponential run time. Even more difficult are the
446:
given the right information, or equivalently, whose solution can be found in polynomial time on a
5470:
3742:
3272:
2117:
1511:
1337:
1155:
209:
37:
If the solution to a problem is easy to check for correctness, must the problem be easy to solve?
4281:
4260:
3963:
1736:(without any citation), is such an example below. It correctly accepts the NP-complete language
661:
5824:
5407:
5385:
5236:
5195:
5008:
4523:
4483:
4447:
4211:
3660:
3421:
3207:
3199:
1740:. It runs in polynomial time on inputs that are in SUBSET-SUM if and only if P = NP:
1701:
1682:
1317:
800:
624:
559:
516:
290:
3796:
3313:
654:
proved in 1974 that every algorithm that decides the truth of
Presburger statements of length
80:
5819:
5814:
4916:
3238:
1863:
are constants independent of the input string, then we say that the problem can be solved in
1198:). These algorithms were sought long before the concept of NP-completeness was even defined (
769:
751:
The graph isomorphism problem is the computational problem of determining whether two finite
643:
404:
2031:
1539:
fall into one of the following classifications, all insufficient to prove P ≠ NP:
5910:
5809:
5326:
4982:
4964:
4637:
4400:
4252:
4124:
3346:
with a reasonable constant term would be disastrous. On the other hand, a solution that is
3168:
1844:
1716:
1520:
1427:
1178:
1154:, that can solve to optimality many real-world instances in reasonable time. The empirical
360:
316:
201:
5459:
3447:
352:
in his seminal paper "The complexity of theorem proving procedures" (and independently by
8:
5215:
4511:
1515:
1387:
1383:
1174:
974:
780:
700:
158:
5365:
4586:
4404:
1591:
defined a general class of proof techniques for circuit complexity lower bounds, called
4935:
4677:
4465:
4390:
4202:
Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)".
4040:
4021:
3943:
3678:
3527:
3439:
2933:
2286:{\displaystyle t_{M}(w)={\text{ number of steps }}M{\text{ takes to halt on input }}w.}
1847:
with unbounded memory) that produces the correct answer for any input string of length
1737:
1708:
1660:
These barriers lead some computer scientists to suggest the P versus NP problem may be
1584:
1553:
1271:
1163:
1158:(time vs. problem size) of such algorithms can be surprisingly low. An example is the
1011:
647:
568:
86:
3151:∈ NP, and there is another NP-complete problem that can be polynomial-time reduced to
1626:
showed that the main technical tool used in the IP = PSPACE proof, known as
542:
will accept exist? It is in NP because (given an input) it is simple to check whether
5829:
5419:
5354:
5330:
5312:
5280:
5152:
4609:
4599:
4585:
Johnson, David S. (August 2012). "A Brief
History of NP-Completeness, 1954–2012". In
4541:
4416:
4363:
4225:
4101:
3985:
Valiant, Leslie G. (1979). "The complexity of enumeration and reliability problems".
3911:
3839:
3822:
3707:
3517:
3477:
2010:
and a deterministic polynomial-time Turing machine is a deterministic Turing machine
1697:
1689:
1598:
1569:
1159:
970:
765:
756:
733:
4726:
T. P. Baker; J. Gill; R. Solovay (1975). "Relativizations of the P =? NP Question".
4698:, p. 134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995.
4514:(1998). "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete".
4044:
3775:
3682:
5793:
5683:
5615:
5605:
5512:
5395:
5298:
4925:
4801:
4768:
4737:
4669:
4533:
4489:
4469:
4457:
4408:
4221:
4182:
4097:
4067:
4030:
3994:
3947:
3907:
3881:
3863:
3834:
3670:
3531:
3509:
3443:
3431:
2922:
1343:
1166:, which works surprisingly well in practice; despite having exponential worst-case
1143:
1019:
994:
715:
651:
581:
426:
396:
372:
197:
162:
65:
4320:
4256:
4240:
4115:
Babai, László (2018). "Group, graphs, algorithms: the graph isomorphism problem".
1119:{\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}
615:
5788:
5778:
5735:
5725:
5718:
5708:
5698:
5656:
5651:
5646:
5630:
5610:
5588:
5583:
5578:
5566:
5561:
5556:
5551:
5322:
4891:
4493:
4248:
4120:
3929:
3703:
3643:
3639:
3262:
3229:
3159:
is NP-complete. This is a common way of proving some new problem is NP-complete.
2945:
1720:
1647:
1635:
1611:
1494:
1253:
1207:
1167:
796:
788:
727:
704:
567:
in polynomial time. This in turn gives a solution to the problem of partitioning
495:
487:
463:
443:
439:
184:
150:
4986:
4930:
4830:
4085:
3622:
Introduction to the Theory of
Computation, Second Edition, International Edition
1244:
also shows that very simple questions may be settled only by very deep theories.
193:
solved in polynomial time, but the answer could be verified in polynomial time.
5783:
5671:
5593:
5546:
5415:
5342:
4866:
4826:
4389:. Lecture Notes in Computer Science. Vol. 1350. Springer. pp. 22–31.
4187:
4168:
3925:
3225:
2932:
COMPOSITE also happens to be in P, a fact demonstrated by the invention of the
1840:
1619:
1560:
1364:
1249:
1223:
1055:
599:
532:
483:
380:
376:
170:
5466:
4792:
4461:
3624:, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
235:, each of which carries a US$ 1,000,000 prize for the first correct solution.
5894:
5371:
5334:
5294:
5266:
5144:
4695:
4613:
4507:
4137:
4071:
3402:
1623:
1593:
1588:
1578:
998:
479:
442:
consists of all decision problems whose positive solutions are verifiable in
5149:
Mathematics and
Computation: A Theory Revolutionizing Technology and Science
4805:
4438:
Massacci, F.; Marraro, L. (2000). "Logical cryptanalysis as a SAT problem".
4412:
3435:
2963:
is NP-complete if, and only if, the following two conditions are satisfied:
368:
29:
4960:
4773:
4756:
4627:
4277:
3497:
3191:
1733:
1693:
1669:
1461:
1439:
1325:
564:
475:
353:
349:
348:
The precise statement of the P versus NP problem was introduced in 1971 by
205:
5060:
4545:
4537:
4058:
Arvind, Vikraman; Kurur, Piyush P. (2006). "Graph isomorphism is in SPP".
4035:
4016:
3674:
3513:
5661:
5571:
5307:. Series of Books in the Mathematical Sciences (1st ed.). New York:
3854:
I. Holyer (1981). "The NP-completeness of some edge-partition problems".
3651:
1442:(assuming not only a proof, but a practically efficient algorithm) says:
1267:
1031:
1015:. It is a common assumption in complexity theory; but there are caveats.
538:
guaranteed to halt in polynomial time, does a polynomial-size input that
384:
213:
154:
5035:"'Travelling Salesman' movie considers the repercussions if P equals NP"
989:
5773:
5598:
4939:
4681:
4658:
L. R. Foulds (October 1983). "The Heuristic Problem-Solving Approach".
4343:
1631:
1361:
1351:
435:
217:
204:, a proof either way would have profound implications for mathematics,
5304:
Computers and Intractability: A Guide to the Theory of NP-Completeness
594:
running time. In other words, any problem in EXPTIME is solvable by a
5768:
5481:
5276:
3604:
Bulletin of the European Association for Theoretical Computer Science
1836:
1643:
1485:
1227:
721:
221:
166:
5399:
4741:
4673:
4385:
Horie, S.; Watanabe, O. (1997). "Hard instance generation for SAT".
3998:
3880:
3867:
3506:
Proceedings of the Third Annual ACM Symposium on Theory of Computing
2692:
to be in NP, there must be a verifier that runs in polynomial time.
287:, is there at least one legal solution where every row, column, and
5763:
5758:
5703:
5526:
4754:
4395:
1756:// "Polynomial-time" means it returns "yes" in polynomial time when
711:
2638:
is decidable by a deterministic Turing machine in polynomial time.
1001:
suggests that the algorithmic complexity of the problem is O((log(
5753:
5474:
4486:
Theory and Applications of Satisfiability Testing – SAT 2007
3382:
in almost all cases would not pose an immediate practical danger.
1914: for some deterministic polynomial-time Turing machine
1707:
Similarly, NP is the set of languages expressible in existential
1368:
1170:, it runs on par with the best known polynomial-time algorithms.
587:
504:
450:
machine. Clearly, P ⊆ NP. Arguably, the biggest open question in
2227:{\displaystyle T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},|w|=n\}}
1759:// the answer should be "yes", and runs forever when it is "no".
5860:
5855:
5730:
5713:
4272:
4270:
1639:
1615:
434:) solvable on a deterministic sequential machine in a duration
244:
196:
The problem has been called the most important open problem in
161:
on the size of the input to the algorithm (as opposed to, say,
3884:
and D. Lichtenstein (1981). "Computing a perfect strategy for
3129:
there exists a polynomial-time Turing machine that halts with
2950:
There are many equivalent ways of describing NP-completeness.
2450:{\displaystyle x\in L\Leftrightarrow \exists y\in \Sigma ^{*}}
2000:{\displaystyle L(M)=\{w\in \Sigma ^{*}:M{\text{ accepts }}w\}}
1835:
over an alphabet Σ, and outputs "yes" or "no". If there is an
1744:// Algorithm that accepts the NP-complete language SUBSET-SUM.
5850:
5845:
5666:
3057:
if, and only if, the following two conditions are satisfied:
1750:// this is a polynomial-time algorithm if and only if P = NP.
1715:
over relations, functions, and subsets. The languages in the
1634:
symbols and then uses those to analyze the workings. In the
1490:
1324:
A solution showing P = NP could upend the field of
1203:
792:
791:
algorithm. The integer factorization problem is in NP and in
628:
528:
NP-complete, and no fast algorithm for any of them is known.
5441:
4725:
4267:
3956:
Proceedings of the SIAM-AMS Symposium in Applied Mathematics
5678:
5536:
4358:
Balcazar, Jose Luis; Diaz, Josep; Gabarro, Joaquim (1990).
3474:
The Golden Ticket: P, NP, and the Search for the Impossible
1696:
relation. Then, all such languages in P are expressible in
1288:
1284:
243:
Consider the following yes/no problem: given an incomplete
4162:
5693:
5625:
5620:
5541:
5531:
1688:
Consider all languages of finite structures with a fixed
1665:
4907:
Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004).
4119:. World Sci. Publ., Hackensack, NJ. pp. 3319–3336.
2688:
Not all verifiers must be polynomial-time. However, for
1523:
workshop in 2009 studied the status of the five worlds.
993:
The graph shows the running time vs. problem size for a
618:
if it is in EXPTIME, and every problem in EXPTIME has a
4895:
Monografías de la Real Academia de Ciencias de Zaragoza
4790:
4437:
3952:"Super-Exponential Complexity of Presburger Arithmetic"
375:. Gödel asked whether theorem-proving (now known to be
2371:
such that the following two conditions are satisfied:
2360:{\displaystyle R\subset \Sigma ^{*}\times \Sigma ^{*}}
1774:// Note: "Program number M" is the program obtained by
1184:
843:
5374:(1987). "Languages that Capture Complexity Classes".
5091:"P vs NP is Elementary? No— P vs NP is ON Elementary"
5009:"Step 1: Post Elusive Proof. Step 2: Watch Fireworks"
4384:
4088:(1988). "Graph isomorphism is in the low hierarchy".
3352:
3316:
3074:
3025:
2987:
2815:
2709:
2611:
2542:
2475:
2415:
2382:
2327:
2321:∈ NP if, and only if, there exists a binary relation
2241:
2132:
2060:
2034:
1945:
1876:
1068:
816:
664:
454:
concerns the relationship between those two classes:
319:
293:
253:
5076:"What is the P vs. NP problem? Why is it important?"
4562:"The History and Status of the P versus NP question"
3823:"The complexity of completing partial Latin squares"
3820:
1526:
1058:
hides a constant that depends superexponentially on
642:
The problem of deciding the truth of a statement in
149:
means an algorithm that solves the task and runs in
31:
4357:
1711:—that is, second-order logic restricted to exclude
1489:
Diagram of complexity classes provided that P
1332:would break most existing cryptosystems including:
189:, standing for "nondeterministic polynomial time".
5473:from the original on 24 November 2021 – via
4906:
4800:. Proceedings of ACM STOC'2008. pp. 731–740.
4241:"3 A computational view of interior point methods"
4017:"On the structure of polynomial time reducibility"
3984:
3638:
3374:
3338:
3119:{\displaystyle (w\in L'\Leftrightarrow f(w)\in L)}
3118:
3049:
3011:
2906:
2800:
2629:
2597:
2523:
2449:
2401:
2359:
2285:
2226:
2104:
2046:
1999:
1925:
1375:These would need modification or replacement with
1118:
997:of a state-of-the-art, specialized algorithm. The
954:
722:Problems in NP not known to be in P or NP-complete
687:
639:board and similar problems for other board games.
332:
305:
279:
4965:"Prizes Aside, the P-NP Puzzler Has Consequences"
4865:(Technical report). Vol. 714. Archived from
4794:Algebrization: A New Barrier in Complexity Theory
4201:
1807:bits long, the above algorithm will try at least
1768:// Output: "yes" if any subset of S adds up to 0.
1354:, used for the encryption of communications data.
803:known algorithm for integer factorization is the
558:after this problem was proved to be NP-complete,
5892:
5117:"Elementary Solve for X Review: Sines of Murder"
4981:
4558:History of this letter and its translation from
3551:[Problems of Information Transmission].
2155:
984:
779:is the computational problem of determining the
5467:"P vs. NP and the Computational Complexity Zoo"
4854:
3930:"Computational Complexity of Games and Puzzles"
1379:solutions that do not assume P ≠ NP.
5187:
4755:Razborov, Alexander A.; Steven Rudich (1997).
4506:
4341:
4238:
4169:"The disjoint paths problem in quadratic time"
3702:
3502:"The complexity of theorem proving procedures"
3252:problem. This problem has not been solved yet.
1189:Cook provides a restatement of the problem in
590:is the set of all decision problems that have
5497:
5406:
5175:In Proc. of 11th ACM STOC, pp. 249–261, 1979.
3797:"MSc course: Foundations of Computer Science"
3476:. Princeton, NJ: Princeton University Press.
1786:// generated this way, though most do nothing
1726:
1038:is fixed, can be solved in a running time of
111:
5293:
4959:
4696:"A personal view of average-case complexity"
4657:
4163:Kawarabayashi, Ken-ichi; Kobayashi, Yusuke;
4147:
3942:
3874:
3597:"Gödel, von Neumann, and the P = NP problem"
2624:
2618:
2592:
2556:
2221:
2158:
1994:
1961:
1920:
1885:
1676:
1312:It is also very possible that a proof would
424:In this theory, the class P consists of all
165:). The general class of questions that some
153:exists, meaning the task completion time is
41:(more unsolved problems in computer science)
5114:
4661:Journal of the Operational Research Society
4598:. Documenta Mathematica. pp. 359–376.
4318:
4057:
4010:
4008:
3544:
1476:bitwise or addition or shift operations on
1294:
421:(it performs actions one after the other).
200:. Aside from being an important problem in
5504:
5490:
5451:Hardness of Approximation Between P and NP
5439:
4245:Advances in linear and integer programming
3924:
3773:
3244:A similar problem exists in the theory of
1780:// considering that string of bits to be a
118:
104:
5389:
5341:
5143:
4929:
4772:
4527:
4451:
4394:
4261:at McMaster University website of Terlaky
4215:
4186:
4034:
3853:
3838:
3664:
3425:
2854:
2846:
2754:
2598:{\displaystyle L_{R}=\{x\#y:(x,y)\in R\}}
2315:be a language over a finite alphabet, Σ.
1783:// program. Every possible program can be
1771:// Runs forever with no output otherwise.
5370:
5139:
5137:
5058:
4084:
4005:
3737:
3735:
3268:List of unsolved problems in mathematics
2957:be a language over a finite alphabet Σ.
1777:// writing the integer M in binary, then
1484:
988:
474:
5088:
5006:
5000:
4949:from the original on 26 September 2006.
4900:
4761:Journal of Computer and System Sciences
4584:
4239:Gondzio, Jacek; Terlaky, Tamás (1996).
4142:Complexity Class of the Week: Factoring
4090:Journal of Computer and System Sciences
3776:"PHYS771 Lecture 6: P, NP, and Friends"
3743:"Guest Column: The Third P =? NP Poll1"
3471:
3407:"The status of the P versus NP problem"
3401:
1510:P ≠ NP still leaves open the
431:
313:square contains the integers 1 through
14:
5906:Computer-related introductions in 1956
5893:
5511:
5265:
5073:
4855:Ben-David, Shai; Halevi, Shai (1992).
4831:"Is P Versus NP Formally Independent?"
4815:from the original on 21 February 2008.
4500:
4014:
3634:
3632:
3630:
2977:in NP is polynomial-time-reducible to
1828:is a problem that takes as input some
1765:// Input: S = a finite set of integers
1700:with the addition of a suitable least
1406:If there really were a machine with φ(
71:Navier–Stokes existence and smoothness
5931:Unsolved problems in computer science
5485:
5213:
5134:
5032:
4843:from the original on 16 January 2017.
4786:
4784:
4626:
4574:from the original on 2 February 2014.
4300:from the original on 16 December 2013
4257:Postscript file at website of Gondzio
4156:
4114:
3767:
3732:
3728:from the original on 24 January 2014.
3696:
3594:
3584:from the original on 9 November 2018.
3278:Unsolved problems in computer science
3205:In the second episode of season 2 of
1814:
5115:Kirkpatrick, Noel (4 October 2013).
4825:
4276:
4051:
3496:
3162:
2939:
2105:{\displaystyle T_{M}(n)\in O(n^{k})}
438:in the size of the input; the class
61:Birch and Swinnerton-Dyer conjecture
32:Unsolved problem in computer science
27:Unsolved problem in computer science
5214:Hosch, William L (11 August 2009).
5089:Gasarch, William (7 October 2013).
5059:Hardesty, Larry (29 October 2009).
4342:Scott Aaronson (4 September 2006).
3892:chess requires time exponential in
3627:
3569:
3218:
1185:Reasons to believe P ≠ NP or P = NP
24:
5259:
5074:Shadia, Ajam (13 September 2013).
4858:On the independence of P versus NP
4791:S. Aaronson; A. Wigderson (2008).
4781:
4559:
3755:from the original on 31 March 2019
3692:from the original on 15 June 2007.
3353:
3175:
3064: : Σ* → Σ* such that for all
2735:
2732:
2729:
2726:
2723:
2720:
2717:
2714:
2711:
2630:{\displaystyle \Sigma \cup \{\#\}}
2621:
2612:
2562:
2438:
2428:
2390:
2348:
2335:
2274: takes to halt on input
2190:
1971:
1386:are NP-complete, such as types of
620:polynomial-time many-one reduction
575:
470:
169:can answer in polynomial time is "
25:
5947:
5866:Probabilistically checkable proof
5433:
5216:"P versus NP problem mathematics"
4633:Twenty Questions for Donald Knuth
4140:. Computational Complexity Blog:
2524:{\displaystyle |y|\in O(|x|^{k})}
1527:Results about difficulty of proof
280:{\displaystyle n^{2}\times n^{2}}
92:Yang–Mills existence and mass gap
5936:Unsolved problems in mathematics
5460:2017 Doctoral Dissertation Award
5173:Completeness classes in algebra.
5095:blog.computationalcomplexity.org
5007:Markoff, John (16 August 2010).
2402:{\displaystyle x\in \Sigma ^{*}}
1878:
1377:information-theoretically secure
1062:. The constant is greater than
546:accepts the input by simulating
5165:
5108:
5082:
5067:
5052:
5033:Geere, Duncan (26 April 2012).
5026:
4975:
4953:
4877:
4848:
4819:
4748:
4719:
4701:
4688:
4651:
4620:
4578:
4552:
4477:
4430:
4377:
4351:
4335:
4312:
4232:
4195:
4174:Journal of Combinatorial Theory
4131:
4108:
4078:
3978:
3936:
3918:
3899:Journal of Combinatorial Theory
3847:
3814:
3789:
3304:
3298:nondeterministic Turing machine
2014:that satisfies two conditions:
1664:of standard axiom systems like
1537:computational complexity theory
1278:
401:computational complexity theory
5241:www.claymath.org (Cook, Levin)
5188:Rachel Crowell (28 May 2021).
5151:. Princeton University Press.
4440:Journal of Automated Reasoning
4319:Rosenberger, Jack (May 2012).
3614:
3588:
3563:
3538:
3490:
3465:
3395:
3375:{\displaystyle \Omega (N^{4})}
3369:
3356:
3333:
3320:
3290:
3113:
3104:
3098:
3092:
3075:
2839:
2827:
2642:A Turing machine that decides
2583:
2571:
2518:
2508:
2499:
2495:
2485:
2477:
2425:
2258:
2252:
2211:
2203:
2177:
2171:
2149:
2143:
2099:
2086:
2077:
2071:
1955:
1949:
1909:
1903:
1291:. It is known that DLIN≠NLIN.
1200:Karp's 21 NP-complete problems
1152:Boolean satisfiability problem
1113:
1110:
1107:
1093:
1090:
1084:
1081:
1075:
1072:
923:
920:
914:
902:
871:
865:
610:) is a polynomial function of
513:Boolean satisfiability problem
13:
1:
4029:: 151–171 See Corollary 1.1.
3821:Colbourn, Charles J. (1984).
3548:Универсальные задачи перебора
3389:
1134:is the number of vertices in
1050:is the number of vertices in
969:-bit integer. The best known
777:integer factorization problem
746:integer factorization problem
5926:Structural complexity theory
4494:10.1007/978-3-540-72788-0_36
4226:10.1016/0196-6774(87)90043-5
4102:10.1016/0022-0000(88)90010-4
3912:10.1016/0097-3165(81)90016-9
3840:10.1016/0166-218X(84)90075-1
3827:Discrete Applied Mathematics
3172:attempts have been refuted.
3050:{\displaystyle L'\leq _{p}L}
3012:{\displaystyle L'\leq _{p}L}
2925:is equivalent to of whether
2695:
1789:// because of syntax errors.
1568:. In 1975, Baker, Gill, and
1396:protein structure prediction
1336:Existing implementations of
1196:List of NP-complete problems
807:, which takes expected time
596:deterministic Turing machine
452:theoretical computer science
140:theoretical computer science
7:
4931:10.4007/annals.2004.160.781
4060:Information and Computation
3256:
3137:) on its tape on any input
2266: number of steps
1819:
1392:travelling salesman problem
10:
5952:
5882:List of complexity classes
5442:"Computational complexity"
5351:Cambridge University Press
5347:P, NP, and NP-Completeness
5272:Introduction to Algorithms
5181:
4387:Algorithms and Computation
4290:Clay Mathematics Institute
4243:. In J. E. Beasley (ed.).
4188:10.1016/j.jctb.2011.07.004
2943:
1727:Polynomial-time algorithms
1602:resolve P = NP.
1148:traveling salesman problem
979:quantum complexity classes
805:general number field sieve
742:discrete logarithm problem
725:
688:{\displaystyle 2^{2^{cn}}}
658:has a runtime of at least
579:
493:
390:
343:
238:
233:Clay Mathematics Institute
5921:Millennium Prize Problems
5916:Mathematical optimization
5879:
5838:
5802:
5746:
5639:
5519:
5440:Fortnow, L.; Gasarch, W.
5377:SIAM Journal on Computing
5309:W. H. Freeman and Company
4729:SIAM Journal on Computing
4325:Communications of the ACM
4282:"The P versus NP Problem"
3987:SIAM Journal on Computing
3414:Communications of the ACM
2675:certificate of membership
1677:Logical characterizations
1501:
1303:
1128:Knuth's up-arrow notation
761:polynomial time hierarchy
738:graph isomorphism problem
646:requires even more time.
395:The relation between the
306:{\displaystyle n\times n}
229:Millennium Prize Problems
216:, multimedia processing,
52:Millennium Prize Problems
5871:Interactive proof system
5412:Computational Complexity
4890:16 February 2012 at the
4360:Structural Complexity II
4072:10.1016/j.ic.2006.02.002
3572:"Letters from John Nash"
3547:
3339:{\displaystyle O(N^{2})}
3283:
3189:In the sixth episode of
2775: for integers
1713:universal quantification
1642:proof, they convert the
1468:if you imagine a number
1295:Consequences of solution
614:. A decision problem is
5408:Papadimitriou, Christos
5221:Encyclopædia Britannica
4806:10.1145/1374376.1374481
4462:10.1023/A:1006326723002
4413:10.1007/3-540-63890-3_4
4321:"P vs. NP poll results"
3962:: 27–41. Archived from
3708:"The Second P=?NP poll"
3472:Fortnow, Lance (2013).
3436:10.1145/1562164.1562186
3273:Unique games conjecture
3235:Hilbert's tenth problem
2367:and a positive integer
1512:average-case complexity
1338:public-key cryptography
1191:The P Versus NP Problem
1156:average-case complexity
399:P and NP is studied in
227:It is one of the seven
224:and many other fields.
210:artificial intelligence
5825:Arithmetical hierarchy
5196:scientificamerican.com
4987:"The P-versus-NP page"
4774:10.1006/jcss.1997.1494
3553:Пробл. передачи информ
3376:
3340:
3200:Treehouse of Horror VI
3120:
3051:
3013:
2908:
2802:
2631:
2599:
2525:
2451:
2403:
2361:
2287:
2228:
2106:
2048:
2047:{\displaystyle k\in N}
2001:
1927:
1811:other programs first.
1702:fixed-point combinator
1683:descriptive complexity
1498:
1483:
1452:
1436:
1318:non-constructive proof
1276:
1258:
1232:
1120:
1006:
956:
689:
625:time hierarchy theorem
515:is NP-complete by the
491:
363:wrote a letter to the
334:
307:
281:
208:, algorithm research,
183:in polynomial time is
5820:Grzegorczyk hierarchy
5815:Exponential hierarchy
5747:Considered infeasible
5061:"Explained: P vs. NP"
4917:Annals of Mathematics
4538:10.1089/cmb.1998.5.27
4204:Journal of Algorithms
4036:10.1145/321864.321877
4015:Ladner, R.E. (1975).
3675:10.1145/564585.564599
3514:10.1145/800157.805047
3377:
3341:
3121:
3052:
3014:
2909:
2803:
2632:
2600:
2526:
2452:
2404:
2362:
2288:
2229:
2107:
2049:
2002:
1928:
1488:
1466:
1456:Fermat's Last Theorem
1444:
1404:
1358:Cryptographic hashing
1259:
1242:Fermat's Last Theorem
1237:
1215:
1179:randomized algorithms
1121:
992:
957:
770:quasi-polynomial time
690:
644:Presburger arithmetic
478:
405:theory of computation
379:) could be solved in
335:
333:{\displaystyle n^{2}}
308:
282:
5810:Polynomial hierarchy
5640:Suspected infeasible
4983:Gerhard J. Woeginger
4715:on 15 November 2013.
4592:Optimization Stories
4344:"Reasons to believe"
4144:. 13 September 2002.
3966:on 15 September 2006
3545:L. A. Levin (1973).
3508:. pp. 151–158.
3350:
3314:
3246:algebraic complexity
3169:Gerhard J. Woeginger
3072:
3023:
2985:
2813:
2707:
2609:
2540:
2473:
2413:
2380:
2325:
2239:
2130:
2058:
2032:
2021:halts on all inputs
1943:
1874:
1717:polynomial hierarchy
1618:. However, in 2008,
1521:Princeton University
1428:Entscheidungsproblem
1066:
814:
701:undecidable problems
662:
317:
291:
251:
202:computational theory
5839:Families of classes
5520:Considered feasible
5449:Aviad Rubinstein's
4405:1998cs........9117H
4362:. Springer Verlag.
3944:Fischer, Michael J.
3453:on 24 February 2011
3301:theoretical models.
3183:Travelling Salesman
2917:Whether a value of
2890: divides
1988: accepts
1607:Algebrizing proofs
1554:Relativizing proofs
1516:Russell Impagliazzo
1388:integer programming
1384:operations research
1175:quantum computation
985:Does P mean "easy"?
781:prime factorization
159:polynomial function
132:P versus NP problem
81:Poincaré conjecture
76:P versus NP problem
5513:Complexity classes
5469:. 26 August 2014.
5013:The New York Times
4969:The New York Times
4963:(8 October 2009).
4883:Elvira Mayordomo.
4436:See, for example,
4022:Journal of the ACM
3704:William I. Gasarch
3640:William I. Gasarch
3595:Hartmanis, Juris.
3372:
3336:
3147:Alternatively, if
3116:
3047:
3009:
2934:AKS primality test
2904:
2798:
2627:
2595:
2521:
2447:
2399:
2357:
2283:
2224:
2102:
2044:
1997:
1923:
1815:Formal definitions
1709:second-order logic
1585:Alexander Razborov
1499:
1448:CMI prize problems
1360:, which underlies
1272:Cornell University
1206:and P =
1164:linear programming
1116:
1091:↑ ↑
1082:↑ ↑
1073:↑ ↑
1007:
973:for this problem,
952:
857:
695:for some constant
685:
569:tri-partite graphs
560:proof by reduction
517:Cook–Levin theorem
511:For instance, the
492:
403:, the part of the
397:complexity classes
330:
303:
277:
87:Riemann hypothesis
5901:1956 in computing
5888:
5887:
5830:Boolean hierarchy
5803:Class hierarchies
5425:978-0-201-53082-7
5360:978-0-521-12254-2
5299:Johnson, David S.
5295:Garey, Michael R.
5286:978-0-262-03293-3
5237:"P vs NP Problem"
5158:978-0-691-18913-0
4897:26: 57–68 (2004).
4605:978-3-936609-58-5
4560:Sipser, Michael.
4422:978-3-540-63890-2
3948:Rabin, Michael O.
3620:Sipser, Michael:
3163:Claimed solutions
2891:
2883:
2878:
2776:
2275:
2267:
1989:
1915:
1698:first-order logic
1654:
1653:
1599:one-way functions
1344:Symmetric ciphers
1262:methods required.
1160:simplex algorithm
971:quantum algorithm
939:
887:
856:
734:Richard E. Ladner
458:Is P equal to NP?
448:non-deterministic
427:decision problems
128:
127:
16:(Redirected from
5943:
5506:
5499:
5492:
5483:
5482:
5478:
5454:, winner of the
5445:
5429:
5403:
5393:
5364:
5338:
5290:
5255:
5249:
5247:
5232:
5230:
5228:
5210:
5205:
5203:
5176:
5169:
5163:
5162:
5141:
5132:
5131:
5129:
5127:
5112:
5106:
5105:
5103:
5101:
5086:
5080:
5079:
5071:
5065:
5064:
5056:
5050:
5049:
5047:
5045:
5030:
5024:
5023:
5021:
5019:
5004:
4998:
4997:
4995:
4993:
4979:
4973:
4972:
4957:
4951:
4950:
4948:
4933:
4913:
4909:"PRIMES is in P"
4904:
4898:
4881:
4875:
4873:
4872:on 2 March 2012.
4871:
4852:
4846:
4844:
4842:
4835:
4823:
4817:
4816:
4814:
4799:
4788:
4779:
4778:
4776:
4757:"Natural proofs"
4752:
4746:
4745:
4723:
4717:
4716:
4711:. Archived from
4705:
4699:
4694:R. Impagliazzo,
4692:
4686:
4685:
4655:
4649:
4648:
4646:
4644:
4628:Knuth, Donald E.
4624:
4618:
4617:
4597:
4582:
4576:
4575:
4573:
4566:
4556:
4550:
4549:
4531:
4504:
4498:
4497:
4481:
4475:
4473:
4455:
4434:
4428:
4426:
4398:
4381:
4375:
4373:
4355:
4349:
4347:
4339:
4333:
4332:
4316:
4310:
4309:
4307:
4305:
4299:
4286:
4274:
4265:
4264:
4236:
4230:
4229:
4219:
4199:
4193:
4192:
4190:
4160:
4154:
4151:
4145:
4135:
4129:
4128:
4112:
4106:
4105:
4082:
4076:
4075:
4055:
4049:
4048:
4038:
4012:
4003:
4002:
3982:
3976:
3975:
3973:
3971:
3940:
3934:
3933:
3922:
3916:
3915:
3882:Aviezri Fraenkel
3878:
3872:
3871:
3851:
3845:
3844:
3842:
3818:
3812:
3811:
3809:
3807:
3793:
3787:
3786:
3784:
3782:
3774:Scott Aaronson.
3771:
3765:
3764:
3762:
3760:
3754:
3747:
3739:
3730:
3729:
3727:
3712:
3700:
3694:
3693:
3691:
3668:
3648:
3644:"The P=?NP poll"
3636:
3625:
3618:
3612:
3611:
3601:
3592:
3586:
3585:
3583:
3576:
3567:
3561:
3560:
3542:
3536:
3535:
3494:
3488:
3487:
3469:
3463:
3462:
3460:
3458:
3452:
3446:. Archived from
3429:
3411:
3399:
3383:
3381:
3379:
3378:
3373:
3368:
3367:
3345:
3343:
3342:
3337:
3332:
3331:
3308:
3302:
3294:
3219:Similar problems
3198:seventh season "
3197:
3125:
3123:
3122:
3117:
3091:
3056:
3054:
3053:
3048:
3043:
3042:
3033:
3018:
3016:
3015:
3010:
3005:
3004:
2995:
2913:
2911:
2910:
2905:
2900:
2896:
2892:
2889:
2884:
2881:
2879:
2874:
2857:
2849:
2807:
2805:
2804:
2799:
2797:
2793:
2777:
2774:
2757:
2738:
2637:
2636:
2634:
2633:
2628:
2604:
2602:
2601:
2596:
2552:
2551:
2531:
2530:
2528:
2527:
2522:
2517:
2516:
2511:
2502:
2488:
2480:
2456:
2454:
2453:
2448:
2446:
2445:
2408:
2406:
2405:
2400:
2398:
2397:
2366:
2364:
2363:
2358:
2356:
2355:
2343:
2342:
2292:
2290:
2289:
2284:
2276:
2273:
2268:
2265:
2251:
2250:
2233:
2231:
2230:
2225:
2214:
2206:
2198:
2197:
2170:
2169:
2142:
2141:
2111:
2109:
2108:
2103:
2098:
2097:
2070:
2069:
2053:
2051:
2050:
2045:
2006:
2004:
2003:
1998:
1990:
1987:
1979:
1978:
1932:
1930:
1929:
1924:
1916:
1913:
1881:
1845:computer program
1826:decision problem
1810:
1542:
1541:
1495:Ladner's theorem
1481:nonconstructive.
1365:cryptocurrencies
1274:
1256:
1230:
1144:knapsack problem
1125:
1123:
1122:
1117:
1103:
1054:. However, the
1022:whether a graph
995:knapsack problem
975:Shor's algorithm
961:
959:
958:
953:
951:
947:
946:
942:
941:
940:
932:
930:
926:
889:
888:
880:
878:
874:
858:
852:
844:
694:
692:
691:
686:
684:
683:
682:
681:
631:positions on an
616:EXPTIME-complete
602:(2) time, where
582:Complexity class
373:John von Neumann
339:
337:
336:
331:
329:
328:
312:
310:
309:
304:
286:
284:
283:
278:
276:
275:
263:
262:
231:selected by the
198:computer science
163:exponential time
136:unsolved problem
120:
113:
106:
66:Hodge conjecture
48:
47:
33:
21:
5951:
5950:
5946:
5945:
5944:
5942:
5941:
5940:
5891:
5890:
5889:
5884:
5875:
5834:
5798:
5742:
5736:PSPACE-complete
5635:
5515:
5510:
5465:
5436:
5426:
5400:10.1137/0216051
5361:
5343:Goldreich, Oded
5319:
5287:
5262:
5260:Further reading
5245:
5243:
5235:
5226:
5224:
5201:
5199:
5184:
5179:
5171:L. G. Valiant.
5170:
5166:
5159:
5142:
5135:
5125:
5123:
5113:
5109:
5099:
5097:
5087:
5083:
5072:
5068:
5057:
5053:
5043:
5041:
5031:
5027:
5017:
5015:
5005:
5001:
4991:
4989:
4980:
4976:
4958:
4954:
4946:
4911:
4905:
4901:
4892:Wayback Machine
4882:
4878:
4869:
4853:
4849:
4840:
4833:
4827:Aaronson, Scott
4824:
4820:
4812:
4797:
4789:
4782:
4753:
4749:
4742:10.1137/0204037
4724:
4720:
4707:
4706:
4702:
4693:
4689:
4674:10.2307/2580891
4668:(10): 927–934.
4656:
4652:
4642:
4640:
4630:(20 May 2014).
4625:
4621:
4606:
4595:
4583:
4579:
4571:
4564:
4557:
4553:
4529:10.1.1.139.5547
4516:J. Comput. Biol
4505:
4501:
4482:
4478:
4435:
4431:
4423:
4382:
4378:
4370:
4356:
4352:
4340:
4336:
4317:
4313:
4303:
4301:
4297:
4284:
4275:
4268:
4237:
4233:
4217:10.1.1.114.3864
4200:
4196:
4161:
4157:
4152:
4148:
4136:
4132:
4113:
4109:
4083:
4079:
4056:
4052:
4013:
4006:
3999:10.1137/0208032
3983:
3979:
3969:
3967:
3941:
3937:
3923:
3919:
3879:
3875:
3868:10.1137/0210054
3852:
3848:
3819:
3815:
3805:
3803:
3801:www.cs.ox.ac.uk
3795:
3794:
3790:
3780:
3778:
3772:
3768:
3758:
3756:
3752:
3745:
3741:
3740:
3733:
3725:
3710:
3701:
3697:
3689:
3666:10.1.1.172.1005
3646:
3637:
3628:
3619:
3615:
3599:
3593:
3589:
3581:
3574:
3568:
3564:
3549:
3543:
3539:
3524:
3495:
3491:
3484:
3470:
3466:
3456:
3454:
3450:
3409:
3400:
3396:
3392:
3387:
3386:
3363:
3359:
3351:
3348:
3347:
3327:
3323:
3315:
3312:
3311:
3309:
3305:
3295:
3291:
3286:
3263:Game complexity
3259:
3221:
3195:
3178:
3176:Popular culture
3165:
3084:
3073:
3070:
3069:
3068:in Σ* we have:
3038:
3034:
3026:
3024:
3021:
3020:
3000:
2996:
2988:
2986:
2983:
2982:
2948:
2946:NP-completeness
2942:
2940:NP-completeness
2888:
2882: and
2880:
2873:
2853:
2845:
2826:
2822:
2814:
2811:
2810:
2773:
2753:
2746:
2742:
2710:
2708:
2705:
2704:
2698:
2647:
2610:
2607:
2606:
2547:
2543:
2541:
2538:
2537:
2512:
2507:
2506:
2498:
2484:
2476:
2474:
2471:
2470:
2441:
2437:
2414:
2411:
2410:
2393:
2389:
2381:
2378:
2377:
2351:
2347:
2338:
2334:
2326:
2323:
2322:
2272:
2264:
2246:
2242:
2240:
2237:
2236:
2210:
2202:
2193:
2189:
2165:
2161:
2137:
2133:
2131:
2128:
2127:
2093:
2089:
2065:
2061:
2059:
2056:
2055:
2033:
2030:
2029:
1986:
1974:
1970:
1944:
1941:
1940:
1912:
1877:
1875:
1872:
1871:
1865:polynomial time
1822:
1817:
1808:
1793:
1729:
1679:
1648:time complexity
1628:arithmetization
1545:Classification
1529:
1504:
1306:
1297:
1281:
1275:
1266:
1257:
1254:Rice University
1248:
1231:
1222:
1187:
1168:time complexity
1099:
1067:
1064:
1063:
1012:Cobham's thesis
987:
931:
895:
891:
890:
879:
845:
842:
841:
837:
836:
835:
831:
824:
820:
815:
812:
811:
730:
728:NP-intermediate
724:
705:halting problem
674:
670:
669:
665:
663:
660:
659:
584:
578:
576:Harder problems
498:
496:NP-completeness
473:
471:NP-completeness
464:William Gasarch
444:polynomial time
393:
346:
324:
320:
318:
315:
314:
292:
289:
288:
271:
267:
258:
254:
252:
249:
248:
241:
151:polynomial time
124:
44:
43:
38:
35:
28:
23:
22:
15:
12:
11:
5:
5949:
5939:
5938:
5933:
5928:
5923:
5918:
5913:
5908:
5903:
5886:
5885:
5880:
5877:
5876:
5874:
5873:
5868:
5863:
5858:
5853:
5848:
5842:
5840:
5836:
5835:
5833:
5832:
5827:
5822:
5817:
5812:
5806:
5804:
5800:
5799:
5797:
5796:
5791:
5786:
5781:
5776:
5771:
5766:
5761:
5756:
5750:
5748:
5744:
5743:
5741:
5740:
5739:
5738:
5728:
5723:
5722:
5721:
5711:
5706:
5701:
5696:
5691:
5686:
5681:
5676:
5675:
5674:
5672:co-NP-complete
5669:
5664:
5659:
5649:
5643:
5641:
5637:
5636:
5634:
5633:
5628:
5623:
5618:
5613:
5608:
5603:
5602:
5601:
5591:
5586:
5581:
5576:
5575:
5574:
5564:
5559:
5554:
5549:
5544:
5539:
5534:
5529:
5523:
5521:
5517:
5516:
5509:
5508:
5501:
5494:
5486:
5480:
5479:
5463:
5446:
5435:
5434:External links
5432:
5431:
5430:
5424:
5416:Addison-Wesley
5404:
5391:10.1.1.75.3035
5384:(4): 760–778.
5372:Immerman, Neil
5368:
5359:
5339:
5317:
5291:
5285:
5267:Cormen, Thomas
5261:
5258:
5257:
5256:
5233:
5211:
5183:
5180:
5178:
5177:
5164:
5157:
5145:Wigderson, Avi
5133:
5107:
5081:
5066:
5051:
5025:
4999:
4974:
4952:
4924:(2): 781–793.
4899:
4876:
4847:
4818:
4780:
4747:
4736:(4): 431–442.
4718:
4700:
4687:
4650:
4619:
4604:
4577:
4551:
4499:
4476:
4453:10.1.1.104.962
4446:(1): 165–203.
4429:
4421:
4376:
4368:
4350:
4334:
4311:
4280:(April 2000).
4266:
4231:
4210:(2): 285–303.
4194:
4181:(2): 424–435.
4155:
4146:
4130:
4107:
4096:(3): 312–323.
4077:
4066:(5): 835–852.
4050:
4004:
3993:(3): 410–421.
3977:
3935:
3926:David Eppstein
3917:
3906:(2): 199–214.
3873:
3862:(4): 713–717.
3856:SIAM J. Comput
3846:
3813:
3788:
3766:
3731:
3695:
3626:
3613:
3587:
3562:
3555:(in Russian).
3537:
3522:
3489:
3482:
3464:
3427:10.1.1.156.767
3403:Fortnow, Lance
3393:
3391:
3388:
3385:
3384:
3371:
3366:
3362:
3358:
3355:
3335:
3330:
3326:
3322:
3319:
3303:
3288:
3287:
3285:
3282:
3281:
3280:
3275:
3270:
3265:
3258:
3255:
3254:
3253:
3242:
3220:
3217:
3177:
3174:
3164:
3161:
3145:
3144:
3143:
3142:
3127:
3115:
3112:
3109:
3106:
3103:
3100:
3097:
3094:
3090:
3087:
3083:
3080:
3077:
3046:
3041:
3037:
3032:
3029:
3008:
3003:
2999:
2994:
2991:
2971:
2944:Main article:
2941:
2938:
2915:
2914:
2903:
2899:
2895:
2887:
2877:
2872:
2869:
2866:
2863:
2860:
2856:
2852:
2848:
2844:
2841:
2838:
2835:
2832:
2829:
2825:
2821:
2818:
2808:
2796:
2792:
2789:
2786:
2783:
2780:
2772:
2769:
2766:
2763:
2760:
2756:
2752:
2749:
2745:
2741:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2713:
2697:
2694:
2645:
2640:
2639:
2626:
2623:
2620:
2617:
2614:
2594:
2591:
2588:
2585:
2582:
2579:
2576:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2550:
2546:
2533:
2520:
2515:
2510:
2505:
2501:
2497:
2494:
2491:
2487:
2483:
2479:
2444:
2440:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2396:
2392:
2388:
2385:
2354:
2350:
2346:
2341:
2337:
2333:
2330:
2296:
2295:
2294:
2293:
2282:
2279:
2271:
2263:
2260:
2257:
2254:
2249:
2245:
2234:
2223:
2220:
2217:
2213:
2209:
2205:
2201:
2196:
2192:
2188:
2185:
2182:
2179:
2176:
2173:
2168:
2164:
2160:
2157:
2154:
2151:
2148:
2145:
2140:
2136:
2122:
2121:
2118:big O notation
2116:refers to the
2101:
2096:
2092:
2088:
2085:
2082:
2079:
2076:
2073:
2068:
2064:
2043:
2040:
2037:
2026:
2008:
2007:
1996:
1993:
1985:
1982:
1977:
1973:
1969:
1966:
1963:
1960:
1957:
1954:
1951:
1948:
1934:
1933:
1922:
1919:
1911:
1908:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1880:
1841:Turing machine
1821:
1818:
1816:
1813:
1798:semi-algorithm
1742:
1728:
1725:
1678:
1675:
1652:
1651:
1620:Scott Aaronson
1608:
1604:
1603:
1594:natural proofs
1581:
1579:Natural proofs
1575:
1574:
1556:
1550:
1549:
1546:
1528:
1525:
1503:
1500:
1373:
1372:
1355:
1341:
1305:
1302:
1296:
1293:
1280:
1277:
1264:
1250:Moshe Y. Vardi
1246:
1224:Scott Aaronson
1220:
1186:
1183:
1115:
1112:
1109:
1106:
1102:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1056:big O notation
986:
983:
963:
962:
950:
945:
938:
935:
929:
925:
922:
919:
916:
913:
910:
907:
904:
901:
898:
894:
886:
883:
877:
873:
870:
867:
864:
861:
855:
851:
848:
840:
834:
830:
827:
823:
819:
726:Main article:
723:
720:
703:, such as the
680:
677:
673:
668:
577:
574:
533:Turing machine
494:Main article:
472:
469:
460:
459:
392:
389:
377:co-NP-complete
345:
342:
327:
323:
302:
299:
296:
274:
270:
266:
261:
257:
240:
237:
126:
125:
123:
122:
115:
108:
100:
97:
96:
95:
94:
89:
84:
78:
73:
68:
63:
55:
54:
39:
36:
30:
26:
9:
6:
4:
3:
2:
5948:
5937:
5934:
5932:
5929:
5927:
5924:
5922:
5919:
5917:
5914:
5912:
5909:
5907:
5904:
5902:
5899:
5898:
5896:
5883:
5878:
5872:
5869:
5867:
5864:
5862:
5859:
5857:
5854:
5852:
5849:
5847:
5844:
5843:
5841:
5837:
5831:
5828:
5826:
5823:
5821:
5818:
5816:
5813:
5811:
5808:
5807:
5805:
5801:
5795:
5792:
5790:
5787:
5785:
5782:
5780:
5777:
5775:
5772:
5770:
5767:
5765:
5762:
5760:
5757:
5755:
5752:
5751:
5749:
5745:
5737:
5734:
5733:
5732:
5729:
5727:
5724:
5720:
5717:
5716:
5715:
5712:
5710:
5707:
5705:
5702:
5700:
5697:
5695:
5692:
5690:
5687:
5685:
5682:
5680:
5677:
5673:
5670:
5668:
5665:
5663:
5660:
5658:
5655:
5654:
5653:
5650:
5648:
5645:
5644:
5642:
5638:
5632:
5629:
5627:
5624:
5622:
5619:
5617:
5614:
5612:
5609:
5607:
5604:
5600:
5597:
5596:
5595:
5592:
5590:
5587:
5585:
5582:
5580:
5577:
5573:
5570:
5569:
5568:
5565:
5563:
5560:
5558:
5555:
5553:
5550:
5548:
5545:
5543:
5540:
5538:
5535:
5533:
5530:
5528:
5525:
5524:
5522:
5518:
5514:
5507:
5502:
5500:
5495:
5493:
5488:
5487:
5484:
5476:
5472:
5468:
5464:
5461:
5457:
5453:
5452:
5447:
5443:
5438:
5437:
5427:
5421:
5417:
5413:
5409:
5405:
5401:
5397:
5392:
5387:
5383:
5379:
5378:
5373:
5369:
5367:
5366:Online drafts
5362:
5356:
5352:
5349:. Cambridge:
5348:
5344:
5340:
5336:
5332:
5328:
5324:
5320:
5318:9780716710455
5314:
5310:
5306:
5305:
5300:
5296:
5292:
5288:
5282:
5278:
5275:. Cambridge:
5274:
5273:
5268:
5264:
5263:
5254:
5242:
5238:
5234:
5223:
5222:
5217:
5212:
5209:
5198:
5197:
5191:
5186:
5185:
5174:
5168:
5160:
5154:
5150:
5146:
5140:
5138:
5122:
5118:
5111:
5096:
5092:
5085:
5077:
5070:
5062:
5055:
5040:
5036:
5029:
5014:
5010:
5003:
4988:
4984:
4978:
4970:
4966:
4962:
4956:
4945:
4941:
4937:
4932:
4927:
4923:
4919:
4918:
4910:
4903:
4896:
4893:
4889:
4886:
4885:"P versus NP"
4880:
4868:
4864:
4860:
4859:
4851:
4839:
4832:
4828:
4822:
4811:
4807:
4803:
4796:
4795:
4787:
4785:
4775:
4770:
4766:
4762:
4758:
4751:
4743:
4739:
4735:
4731:
4730:
4722:
4714:
4710:
4704:
4697:
4691:
4683:
4679:
4675:
4671:
4667:
4663:
4662:
4654:
4639:
4635:
4634:
4629:
4623:
4615:
4611:
4607:
4601:
4594:
4593:
4588:
4587:Grötschel, M.
4581:
4570:
4563:
4555:
4547:
4543:
4539:
4535:
4530:
4525:
4521:
4517:
4513:
4509:
4503:
4495:
4491:
4487:
4480:
4471:
4467:
4463:
4459:
4454:
4449:
4445:
4441:
4433:
4424:
4418:
4414:
4410:
4406:
4402:
4397:
4392:
4388:
4380:
4374:, Theorem 3.9
4371:
4369:3-540-52079-1
4365:
4361:
4354:
4345:
4338:
4330:
4326:
4322:
4315:
4296:
4292:
4291:
4283:
4279:
4278:Cook, Stephen
4273:
4271:
4262:
4258:
4254:
4250:
4246:
4242:
4235:
4227:
4223:
4218:
4213:
4209:
4205:
4198:
4189:
4184:
4180:
4176:
4175:
4170:
4166:
4159:
4150:
4143:
4139:
4138:Lance Fortnow
4134:
4126:
4122:
4118:
4111:
4103:
4099:
4095:
4091:
4087:
4086:Schöning, Uwe
4081:
4073:
4069:
4065:
4061:
4054:
4046:
4042:
4037:
4032:
4028:
4024:
4023:
4018:
4011:
4009:
4000:
3996:
3992:
3988:
3981:
3965:
3961:
3957:
3953:
3949:
3945:
3939:
3931:
3927:
3921:
3913:
3909:
3905:
3901:
3900:
3895:
3891:
3887:
3883:
3877:
3869:
3865:
3861:
3857:
3850:
3841:
3836:
3832:
3828:
3824:
3817:
3802:
3798:
3792:
3777:
3770:
3751:
3744:
3738:
3736:
3724:
3720:
3716:
3709:
3705:
3699:
3688:
3684:
3680:
3676:
3672:
3667:
3662:
3658:
3654:
3653:
3645:
3642:(June 2002).
3641:
3635:
3633:
3631:
3623:
3617:
3609:
3605:
3598:
3591:
3580:
3573:
3566:
3559:(3): 115–116.
3558:
3554:
3550:
3541:
3533:
3529:
3525:
3523:9781450374644
3519:
3515:
3511:
3507:
3503:
3499:
3498:Cook, Stephen
3493:
3485:
3483:9780691156491
3479:
3475:
3468:
3449:
3445:
3441:
3437:
3433:
3428:
3423:
3419:
3415:
3408:
3404:
3398:
3394:
3364:
3360:
3328:
3324:
3317:
3307:
3299:
3293:
3289:
3279:
3276:
3274:
3271:
3269:
3266:
3264:
3261:
3260:
3251:
3247:
3243:
3240:
3236:
3232:
3231:
3227:
3223:
3222:
3216:
3214:
3213:"Solve for X"
3210:
3209:
3203:
3201:
3194:
3193:
3187:
3185:
3184:
3173:
3170:
3160:
3158:
3154:
3150:
3140:
3136:
3132:
3128:
3110:
3107:
3101:
3095:
3088:
3085:
3081:
3078:
3067:
3063:
3060:There exists
3059:
3058:
3044:
3039:
3035:
3030:
3027:
3006:
3001:
2997:
2992:
2989:
2980:
2976:
2972:
2969:
2966:
2965:
2964:
2962:
2958:
2956:
2951:
2947:
2937:
2935:
2930:
2928:
2924:
2920:
2901:
2897:
2893:
2885:
2875:
2870:
2867:
2864:
2861:
2858:
2850:
2842:
2836:
2833:
2830:
2823:
2819:
2816:
2809:
2794:
2790:
2787:
2784:
2781:
2778:
2770:
2767:
2764:
2761:
2758:
2750:
2747:
2743:
2739:
2703:
2702:
2701:
2693:
2691:
2686:
2684:
2680:
2676:
2672:
2668:
2664:
2660:
2656:
2652:
2648:
2615:
2589:
2586:
2580:
2577:
2574:
2568:
2565:
2559:
2553:
2548:
2544:
2535:the language
2534:
2513:
2503:
2492:
2489:
2481:
2468:
2464:
2460:
2442:
2434:
2431:
2422:
2419:
2416:
2394:
2386:
2383:
2374:
2373:
2372:
2370:
2352:
2344:
2339:
2331:
2328:
2320:
2316:
2314:
2309:
2307:
2303:
2302:
2280:
2277:
2269:
2261:
2255:
2247:
2243:
2235:
2218:
2215:
2207:
2199:
2194:
2186:
2183:
2180:
2174:
2166:
2162:
2152:
2146:
2138:
2134:
2126:
2125:
2124:
2123:
2119:
2115:
2094:
2090:
2083:
2080:
2074:
2066:
2062:
2041:
2038:
2035:
2028:there exists
2027:
2024:
2020:
2017:
2016:
2015:
2013:
1991:
1983:
1980:
1975:
1967:
1964:
1958:
1952:
1946:
1939:
1938:
1937:
1917:
1906:
1900:
1897:
1894:
1891:
1888:
1882:
1870:
1869:
1868:
1866:
1862:
1858:
1855:steps, where
1854:
1850:
1846:
1842:
1838:
1834:
1831:
1827:
1812:
1806:
1801:
1799:
1790:
1787:
1784:
1781:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1741:
1739:
1735:
1724:
1722:
1718:
1714:
1710:
1705:
1703:
1699:
1695:
1691:
1686:
1684:
1674:
1671:
1667:
1663:
1658:
1649:
1645:
1641:
1638: =
1637:
1633:
1629:
1625:
1624:Avi Wigderson
1621:
1617:
1614: =
1613:
1609:
1606:
1605:
1600:
1596:
1595:
1590:
1589:Steven Rudich
1586:
1582:
1580:
1577:
1576:
1571:
1567:
1563:
1562:
1557:
1555:
1552:
1551:
1547:
1544:
1543:
1540:
1538:
1533:
1524:
1522:
1517:
1513:
1508:
1496:
1492:
1487:
1482:
1479:
1475:
1471:
1465:
1463:
1459:
1457:
1451:
1449:
1443:
1441:
1435:
1433:
1429:
1425:
1421:
1417:
1413:
1409:
1403:
1399:
1397:
1393:
1389:
1385:
1380:
1378:
1370:
1366:
1363:
1359:
1356:
1353:
1349:
1345:
1342:
1339:
1335:
1334:
1333:
1331:
1327:
1322:
1319:
1315:
1310:
1301:
1292:
1290:
1286:
1273:
1269:
1263:
1255:
1251:
1245:
1243:
1236:
1229:
1225:
1219:
1214:
1211:
1209:
1205:
1201:
1197:
1192:
1182:
1180:
1176:
1171:
1169:
1165:
1161:
1157:
1153:
1149:
1145:
1139:
1137:
1133:
1130:), and where
1129:
1104:
1100:
1096:
1087:
1078:
1069:
1061:
1057:
1053:
1049:
1045:
1041:
1037:
1033:
1029:
1025:
1021:
1016:
1014:
1013:
1004:
1000:
999:quadratic fit
996:
991:
982:
980:
976:
972:
968:
965:to factor an
948:
943:
936:
933:
927:
917:
911:
908:
905:
899:
896:
892:
884:
881:
875:
868:
862:
859:
853:
849:
846:
838:
832:
828:
825:
821:
817:
810:
809:
808:
806:
802:
798:
795:(and even in
794:
790:
786:
782:
778:
773:
771:
767:
762:
758:
754:
749:
747:
743:
739:
735:
729:
719:
717:
713:
708:
706:
702:
698:
678:
675:
671:
666:
657:
653:
649:
645:
640:
638:
634:
630:
626:
621:
617:
613:
609:
605:
601:
597:
593:
589:
583:
573:
570:
566:
565:Latin squares
561:
555:
553:
549:
545:
541:
537:
534:
529:
526:
522:
518:
514:
509:
506:
502:
497:
489:
485:
481:
480:Euler diagram
477:
468:
465:
457:
456:
455:
453:
449:
445:
441:
437:
433:
429:
428:
422:
420:
416:
415:
414:deterministic
409:
406:
402:
398:
388:
386:
382:
378:
374:
370:
366:
362:
357:
355:
351:
341:
325:
321:
300:
297:
294:
272:
268:
264:
259:
255:
247:grid of size
246:
236:
234:
230:
225:
223:
219:
215:
211:
207:
203:
199:
194:
190:
188:
187:
182:
178:
174:
173:
168:
164:
160:
156:
155:bounded above
152:
148:
143:
141:
137:
133:
121:
116:
114:
109:
107:
102:
101:
99:
98:
93:
90:
88:
85:
82:
79:
77:
74:
72:
69:
67:
64:
62:
59:
58:
57:
56:
53:
50:
49:
46:
42:
19:
5450:
5411:
5381:
5375:
5346:
5302:
5271:
5251:
5244:. Retrieved
5240:
5225:. Retrieved
5219:
5207:
5200:. Retrieved
5193:
5172:
5167:
5148:
5124:. Retrieved
5120:
5110:
5098:. Retrieved
5094:
5084:
5069:
5054:
5042:. Retrieved
5038:
5028:
5018:20 September
5016:. Retrieved
5012:
5002:
4990:. Retrieved
4977:
4968:
4961:John Markoff
4955:
4921:
4915:
4902:
4894:
4879:
4867:the original
4862:
4857:
4850:
4821:
4793:
4767:(1): 24–35.
4764:
4760:
4750:
4733:
4727:
4721:
4713:the original
4703:
4690:
4665:
4659:
4653:
4641:. Retrieved
4632:
4622:
4591:
4580:
4554:
4522:(1): 27–40.
4519:
4515:
4512:Leighton, T.
4502:
4485:
4479:
4443:
4439:
4432:
4386:
4379:
4359:
4353:
4337:
4328:
4324:
4314:
4302:. Retrieved
4288:
4244:
4234:
4207:
4203:
4197:
4178:
4177:. Series B.
4172:
4158:
4149:
4133:
4116:
4110:
4093:
4089:
4080:
4063:
4059:
4053:
4026:
4020:
3990:
3986:
3980:
3968:. Retrieved
3964:the original
3959:
3955:
3938:
3920:
3903:
3902:. Series A.
3897:
3893:
3889:
3885:
3876:
3859:
3855:
3849:
3833:(1): 25–30.
3830:
3826:
3816:
3804:. Retrieved
3800:
3791:
3779:. Retrieved
3769:
3757:. Retrieved
3718:
3714:
3698:
3659:(2): 34–47.
3656:
3650:
3621:
3616:
3607:
3603:
3590:
3570:NSA (2012).
3565:
3556:
3552:
3540:
3505:
3492:
3473:
3467:
3455:. Retrieved
3448:the original
3420:(9): 78–86.
3417:
3413:
3397:
3306:
3292:
3249:
3224:
3206:
3204:
3192:The Simpsons
3190:
3188:
3181:
3179:
3166:
3156:
3152:
3148:
3146:
3138:
3134:
3130:
3065:
3061:
2981:(written as
2978:
2974:
2967:
2960:
2959:
2954:
2952:
2949:
2931:
2926:
2918:
2916:
2699:
2689:
2687:
2682:
2678:
2674:
2673:is called a
2670:
2666:
2662:
2658:
2654:
2650:
2649:is called a
2643:
2641:
2466:
2462:
2458:
2368:
2318:
2317:
2312:
2310:
2305:
2299:
2297:
2113:
2022:
2018:
2011:
2009:
1935:
1864:
1860:
1856:
1852:
1848:
1832:
1825:
1823:
1804:
1802:
1797:
1794:
1788:
1785:
1782:
1779:
1776:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1752:
1749:
1746:
1743:
1730:
1706:
1694:linear order
1692:including a
1687:
1680:
1670:Peano axioms
1659:
1655:
1627:
1592:
1566:relativizing
1565:
1559:
1534:
1530:
1509:
1505:
1477:
1473:
1469:
1467:
1462:Donald Knuth
1460:
1453:
1445:
1440:Stephen Cook
1437:
1431:
1423:
1419:
1415:
1411:
1407:
1405:
1400:
1381:
1374:
1326:cryptography
1323:
1313:
1311:
1307:
1298:
1282:
1279:DLIN vs NLIN
1260:
1238:
1233:
1216:
1212:
1190:
1188:
1172:
1140:
1135:
1131:
1059:
1051:
1047:
1043:
1039:
1035:
1027:
1023:
1017:
1010:
1008:
1002:
966:
964:
784:
774:
766:László Babai
750:
731:
709:
696:
655:
641:
636:
632:
611:
607:
603:
591:
585:
556:
551:
547:
543:
539:
535:
530:
524:
523:instance of
520:
510:
503:
499:
462:Since 2002,
461:
425:
423:
418:
412:
410:
394:
358:
354:Leonid Levin
350:Stephen Cook
347:
242:
226:
206:cryptography
195:
191:
185:
180:
176:
171:
146:
144:
131:
129:
75:
45:
5911:Conjectures
5719:#P-complete
5657:NP-complete
5572:NL-complete
4165:Reed, Bruce
3715:SIGACT News
3652:SIGACT News
3239:RE-complete
2661:such that (
2457:such that (
2301:certificate
1851:in at most
1662:independent
1548:Definition
1438:Similarly,
1418:(or even ∼
1268:Anil Nerode
716:#P-complete
592:exponential
385:linear time
214:game theory
134:is a major
18:P versus NP
5895:Categories
5774:ELEMENTARY
5599:P-complete
5414:. Boston:
4508:Berger, B.
4396:cs/9809117
4348:, point 9.
4304:18 October
3970:15 October
3610:: 101–107.
3457:26 January
3390:References
3250:VP vs. VNP
3208:Elementary
2054:such that
1738:SUBSET-SUM
1650:problems.
1632:arithmetic
1362:blockchain
1150:, and the
768:, runs in
757:isomorphic
744:, and the
580:See also:
436:polynomial
419:sequential
369:Kurt Gödel
356:in 1973).
218:philosophy
5769:2-EXPTIME
5386:CiteSeerX
5335:247570676
5277:MIT Press
4614:1431-0643
4524:CiteSeerX
4448:CiteSeerX
4212:CiteSeerX
3781:27 August
3661:CiteSeerX
3422:CiteSeerX
3354:Ω
3237:which is
3180:The film
3108:∈
3093:⇔
3082:∈
3036:≤
3019:), where
2998:≤
2970:∈ NP; and
2923:composite
2871:≤
2859:∣
2851:×
2843:∈
2759:∣
2751:∈
2622:#
2616:∪
2613:Σ
2587:∈
2563:#
2490:∈
2443:∗
2439:Σ
2435:∈
2429:∃
2426:⇔
2420:∈
2395:∗
2391:Σ
2387:∈
2353:∗
2349:Σ
2345:×
2340:∗
2336:Σ
2332:⊂
2195:∗
2191:Σ
2187:∈
2081:∈
2039:∈
1976:∗
1972:Σ
1968:∈
1837:algorithm
1690:signature
1644:black box
1583:In 1993,
1228:UT Austin
1046:), where
1026:contains
912:
900:
863:
829:
801:efficient
732:In 1975,
430:(defined
381:quadratic
361:John Nash
298:×
265:×
222:economics
167:algorithm
5764:EXPSPACE
5759:NEXPTIME
5527:DLOGTIME
5471:Archived
5410:(1994).
5345:(2010).
5301:(1979).
5269:(2001).
5147:(2019).
5044:26 April
5039:Wired UK
4944:Archived
4888:Archived
4863:Technion
4838:Archived
4810:Archived
4638:InformIT
4569:Archived
4331:(5): 10.
4295:Archived
4167:(2012).
4045:14352974
3950:(1974).
3750:Archived
3723:Archived
3687:Archived
3683:36828694
3579:Archived
3500:(1971).
3405:(2009).
3257:See also
3089:′
3031:′
2993:′
2651:verifier
2376:For all
2306:verifier
2112:, where
1820:P and NP
1390:and the
1367:such as
1346:such as
1265:—
1247:—
1221:—
1034:, where
1020:deciding
181:verified
83:(solved)
5754:EXPTIME
5662:NP-hard
5475:YouTube
5327:0519066
5246:20 June
5227:20 June
5202:21 June
5182:Sources
4992:24 June
4940:3597229
4682:2580891
4643:20 July
4589:(ed.).
4546:9541869
4470:3114247
4401:Bibcode
4253:1438311
4125:3966534
3532:7573663
3444:5969255
3155:, then
2696:Example
1843:, or a
1839:(say a
1570:Solovay
1369:Bitcoin
1126:(using
648:Fischer
588:EXPTIME
505:NP-hard
391:Context
344:History
239:Example
177:class P
147:quickly
5861:NSPACE
5856:DSPACE
5731:PSPACE
5422:
5388:
5357:
5333:
5325:
5315:
5283:
5155:
5126:6 July
5121:TV.com
5100:6 July
4938:
4870:(GZIP)
4680:
4612:
4602:
4544:
4526:
4468:
4450:
4419:
4366:
4251:
4214:
4123:
4043:
3806:25 May
3759:25 May
3681:
3663:
3530:
3520:
3480:
3442:
3424:
2657:and a
1936:where
1830:string
1640:PSPACE
1616:PSPACE
1561:oracle
1502:P ≠ NP
1304:P = NP
1218:found.
1146:, the
753:graphs
740:, the
245:Sudoku
175:" or "
145:Here,
5851:NTIME
5846:DTIME
5667:co-NP
4947:(PDF)
4936:JSTOR
4912:(PDF)
4841:(PDF)
4834:(PDF)
4813:(PDF)
4798:(PDF)
4678:JSTOR
4596:(PDF)
4572:(PDF)
4565:(PDF)
4466:S2CID
4391:arXiv
4298:(PDF)
4285:(PDF)
4041:S2CID
3753:(PDF)
3746:(PDF)
3726:(PDF)
3711:(PDF)
3690:(PDF)
3679:S2CID
3647:(PDF)
3600:(PDF)
3582:(PDF)
3575:(PDF)
3528:S2CID
3451:(PDF)
3440:S2CID
3410:(PDF)
3284:Notes
3196:'
3126:; and
2605:over
2532:; and
1809:2 − 1
1734:Levin
1330:3-SAT
1204:co-NP
1194:(see
1032:minor
1030:as a
793:co-NP
652:Rabin
629:chess
519:, so
432:below
157:by a
5679:TFNP
5420:ISBN
5355:ISBN
5331:OCLC
5313:ISBN
5281:ISBN
5248:2021
5229:2021
5204:2021
5194:www.
5153:ISBN
5128:2018
5102:2018
5046:2012
5020:2010
4994:2018
4645:2014
4610:ISSN
4600:ISBN
4542:PMID
4417:ISBN
4383:See
4364:ISBN
4306:2006
4259:and
3972:2017
3808:2020
3783:2007
3761:2020
3518:ISBN
3478:ISBN
3459:2010
3228:vs.
2973:any
2953:Let
2865:<
2788:>
2700:Let
2669:) ∈
2653:for
2469:and
2465:) ∈
2311:Let
2304:and
1859:and
1622:and
1587:and
1410:) ∼
1352:3DES
1289:NLIN
1287:and
1285:DLIN
1177:and
1005:))).
775:The
755:are
650:and
482:for
130:The
5794:ALL
5694:QMA
5684:FNP
5626:APX
5621:BQP
5616:BPP
5606:ZPP
5537:ACC
5458:'s
5456:ACM
5396:doi
4926:doi
4922:160
4802:doi
4769:doi
4738:doi
4670:doi
4534:doi
4490:doi
4458:doi
4409:doi
4222:doi
4183:doi
4179:102
4098:doi
4068:doi
4064:204
4031:doi
3995:doi
3908:doi
3896:".
3864:doi
3835:doi
3671:doi
3510:doi
3432:doi
2921:is
2681:in
2677:of
2156:max
2120:and
2025:and
1800:).
1666:ZFC
1350:or
1348:AES
1314:not
1162:in
909:log
897:log
860:log
826:exp
789:RSA
598:in
525:any
521:any
383:or
371:to
365:NSA
138:in
5897::
5789:RE
5779:PR
5726:IP
5714:#P
5709:PP
5704:⊕P
5699:PH
5689:AM
5652:NP
5647:UP
5631:FP
5611:RP
5589:CC
5584:SC
5579:NC
5567:NL
5562:FL
5557:RL
5552:SL
5542:TC
5532:AC
5418:.
5394:.
5382:16
5380:.
5353:.
5329:.
5323:MR
5321:.
5311:.
5297:;
5279:.
5250:.
5239:.
5218:.
5206:.
5192:.
5136:^
5119:.
5093:.
5037:.
5011:.
4985:.
4967:.
4942:.
4934:.
4920:.
4914:.
4861:.
4836:.
4829:.
4808:.
4783:^
4765:55
4763:.
4759:.
4732:.
4676:.
4666:34
4664:.
4636:.
4608:.
4567:.
4540:.
4532:.
4518:.
4510:;
4464:.
4456:.
4444:24
4442:.
4415:.
4407:.
4399:.
4329:55
4327:.
4323:.
4293:.
4287:.
4269:^
4255:.
4249:MR
4220:.
4206:.
4171:.
4121:MR
4094:37
4092:.
4062:.
4039:.
4027:22
4025:.
4019:.
4007:^
3989:.
3958:.
3954:.
3946:;
3928:.
3904:31
3888:×
3860:10
3858:.
3829:.
3825:.
3799:.
3748:.
3734:^
3721:.
3719:74
3717:.
3713:.
3706:.
3685:.
3677:.
3669:.
3657:33
3655:.
3649:.
3629:^
3608:38
3606:.
3602:.
3577:.
3526:.
3516:.
3504:.
3438:.
3430:.
3418:52
3416:.
3412:.
3296:A
3248::
3230:RE
3211:,
2975:L'
2936:.
2685:.
2665:,
2461:,
2409:,
1853:cn
1824:A
1762://
1753://
1747://
1721:PH
1719:,
1685:.
1636:IP
1612:IP
1270:,
1252:,
1226:,
1210:.
1208:PH
1181:.
1138:.
981:.
847:64
797:UP
772:.
712:#P
635:×
488:NP
486:,
440:NP
220:,
212:,
186:NP
5784:R
5594:P
5547:L
5505:e
5498:t
5491:v
5477:.
5462:.
5444:.
5428:.
5402:.
5398::
5363:.
5337:.
5289:.
5231:.
5161:.
5130:.
5104:.
5078:.
5063:.
5048:.
5022:.
4996:.
4971:.
4928::
4874:.
4845:.
4804::
4777:.
4771::
4744:.
4740::
4734:4
4684:.
4672::
4647:.
4616:.
4548:.
4536::
4520:5
4496:.
4492::
4472:.
4460::
4425:.
4411::
4403::
4393::
4372:.
4346:.
4308:.
4263:.
4228:.
4224::
4208:8
4191:.
4185::
4127:.
4104:.
4100::
4074:.
4070::
4047:.
4033::
4001:.
3997::
3991:8
3974:.
3960:7
3932:.
3914:.
3910::
3894:n
3890:n
3886:n
3870:.
3866::
3843:.
3837::
3831:8
3810:.
3785:.
3763:.
3673::
3557:9
3534:.
3512::
3486:.
3461:.
3434::
3370:)
3365:4
3361:N
3357:(
3334:)
3329:2
3325:N
3321:(
3318:O
3241:.
3226:R
3157:L
3153:L
3149:L
3141:.
3139:w
3135:w
3133:(
3131:f
3114:)
3111:L
3105:)
3102:w
3099:(
3096:f
3086:L
3079:w
3076:(
3066:w
3062:f
3045:L
3040:p
3028:L
3007:L
3002:p
2990:L
2979:L
2968:L
2961:L
2955:L
2927:x
2919:x
2902:.
2898:}
2894:x
2886:y
2876:x
2868:y
2862:1
2855:N
2847:N
2840:)
2837:y
2834:,
2831:x
2828:(
2824:{
2820:=
2817:R
2795:}
2791:1
2785:q
2782:,
2779:p
2771:q
2768:p
2765:=
2762:x
2755:N
2748:x
2744:{
2740:=
2736:E
2733:T
2730:I
2727:S
2724:O
2721:P
2718:M
2715:O
2712:C
2690:L
2683:L
2679:x
2671:R
2667:y
2663:x
2659:y
2655:L
2646:R
2644:L
2625:}
2619:{
2593:}
2590:R
2584:)
2581:y
2578:,
2575:x
2572:(
2569::
2566:y
2560:x
2557:{
2554:=
2549:R
2545:L
2519:)
2514:k
2509:|
2504:x
2500:|
2496:(
2493:O
2486:|
2482:y
2478:|
2467:R
2463:y
2459:x
2432:y
2423:L
2417:x
2384:x
2369:k
2329:R
2319:L
2313:L
2281:.
2278:w
2270:M
2262:=
2259:)
2256:w
2253:(
2248:M
2244:t
2222:}
2219:n
2216:=
2212:|
2208:w
2204:|
2200:,
2184:w
2181::
2178:)
2175:w
2172:(
2167:M
2163:t
2159:{
2153:=
2150:)
2147:n
2144:(
2139:M
2135:T
2114:O
2100:)
2095:k
2091:n
2087:(
2084:O
2078:)
2075:n
2072:(
2067:M
2063:T
2042:N
2036:k
2023:w
2019:M
2012:M
1995:}
1992:w
1984:M
1981::
1965:w
1962:{
1959:=
1956:)
1953:M
1950:(
1947:L
1921:}
1918:M
1910:)
1907:M
1904:(
1901:L
1898:=
1895:L
1892::
1889:L
1886:{
1883:=
1879:P
1861:c
1857:k
1849:n
1833:w
1805:b
1497:.
1491:≠
1478:n
1474:n
1470:M
1450:.
1432:n
1424:n
1422:⋅
1420:k
1416:n
1414:⋅
1412:k
1408:n
1136:H
1132:h
1114:)
1111:)
1108:)
1105:2
1101:/
1097:h
1094:(
1088:2
1085:(
1079:2
1076:(
1070:2
1060:H
1052:G
1048:n
1044:n
1042:(
1040:O
1036:H
1028:H
1024:G
1003:n
967:n
949:)
944:)
937:3
934:2
928:)
924:)
921:)
918:2
915:(
906:n
903:(
893:(
885:3
882:1
876:)
872:)
869:2
866:(
854:9
850:n
839:(
833:(
822:(
818:O
785:k
697:c
679:n
676:c
672:2
667:2
656:n
637:N
633:N
612:n
608:n
606:(
604:p
600:O
552:M
548:M
544:M
540:M
536:M
484:P
326:2
322:n
301:n
295:n
273:2
269:n
260:2
256:n
172:P
119:e
112:t
105:v
34::
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.