P versus NP problem - Knowledge (XXG)

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

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.

1401:

These changes could be insignificant compared to the revolution 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:

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: 117: 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: 5905: 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,

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

135: 40: 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. 5503: 2238: 4660: 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

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

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" 5935: 3267: 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.

110: 5189: 4568: 1394:. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in 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.

91: 5925: 5423: 5358: 5284: 5156: 4603: 4420: 3277: 2308:. Formally, NP is the set of languages with a finite alphabet and verifier that runs in polynomial time. The following defines a "verifier": 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 4884: 3951: 60: 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. 5455: 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) 5920: 5915: 2129: 619: 103: 5865: 5316: 4367: 3521: 3481: 2412: 1942: 1661: 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: 1199: 5496: 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.

447: 4712: 3722: 3186:, by director Timothy Lanzone, is the story of four mathematicians hired by the US government to solve the P versus NP problem. 5090: 4247:. Oxford Lecture Series in Mathematics and its Applications. Vol. 4. New York: Oxford University Press. pp. 103–144. 4173: 3898: 3297: 3182: 1536: 1398:, are also NP-complete; making these problems efficiently solvable could considerably advance life sciences and biotechnology. 400: 1376: 1329: 1151: 512: 3686: 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: 4856: 3245: 783:

of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than

776: 745: 4809: 5303: 3071: 1395: 1347: 1195: 1127: 752: 595: 451: 417:(given the computer's present state and any inputs, there is only one possible action that the computer might take) and 139: 5489: 3212: 1391: 1357: 5688: 5116: 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:

5900: 5881: 5350: 5270: 5220: 4590: 4289: 4164: 3234: 1147: 804: 741: 232: 5075: 5376: 5308: 4728: 1829: 978: 760: 737: 413: 228: 51: 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

5870: 3202:", the equation P = NP is seen shortly after Homer accidentally stumbles into the "third dimension". 2539: 2300: 1712: 364: 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

1455: 1241: 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. 4141: 3272: 1511: 1434:

so large that when the machine does not deliver a result, it makes no sense to think more about the problem.

1337: 1155: 209: 3501: 516: 5824: 5407: 5385: 5195: 4523: 4447: 4211: 4117:

Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures

3660: 3421: 3207: 3199: 2057: 1926:{\displaystyle \mathbf {P} =\{L:L=L(M){\text{ for some deterministic polynomial-time Turing machine }}M\}} 1701: 1682: 1317: 800: 624: 559: 80: 5819: 5814: 4916: 3215:

Sherlock and Watson investigate the murders of mathematicians who were attempting to solve P versus NP.

2608: 769: 643: 404: 3596: 2472: 250: 5448: 5034: 4561: 2379: 977:, runs in polynomial time, although this does not indicate where the problem lies with respect to non- 5910: 5809: 4982: 4709:"Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds"" 4637: 4400: 3168: 1844: 1716: 1520: 1427: 1178: 360: 201: 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

5390: 4586: 4511: 4452: 3426: 1515: 1447: 1387: 1383: 1174: 974: 780: 700: 158: 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: 4935: 4677: 4465: 4390: 4040: 4021: 3943: 3742: 3678: 3527: 3439: 2933: 1737: 1708: 1584: 1553: 1271: 1163: 647: 568: 86: 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 1011: 765: 661: 5236: 5008: 1740:. It runs in polynomial time on inputs that are in SUBSET-SUM if and only if P = NP: 290: 5829: 5419: 5354: 5330: 5312: 5280: 5152: 4609: 4599: 4541: 4416: 4363: 3796: 3517: 3477: 3313: 1697: 1689: 1598: 1569: 1159: 970: 756: 733: 654:

proved in 1974 that every algorithm that decides the truth of Presburger statements of length

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 ( 751:

The graph isomorphism problem is the computational problem of determining whether two finite

5793: 5683: 5615: 5605: 5512: 5395: 5298: 4925: 4801: 4768: 4737: 4669: 4533: 4489: 4457: 4408: 4221: 4182: 4097: 4067: 4030: 3994: 3947: 3907: 3881: 3863: 3834: 3670: 3509: 3431: 2922: 2031: 1539:

fall into one of the following classifications, all insufficient to prove P ≠ NP:

1343: 1143: 1019: 994: 715: 651: 581: 426: 396: 372: 197: 162: 65: 5718: 5326: 4964: 4252: 4124: 3346:

with a reasonable constant term would be disastrous. On the other hand, a solution that is

1154:, that can solve to optimality many real-world instances in reasonable time. The empirical 316: 5788: 5778: 5735: 5725: 5708: 5698: 5656: 5651: 5646: 5630: 5610: 5588: 5583: 5578: 5566: 5561: 5556: 5551: 5459: 5322: 4891: 4248: 4120: 3703: 3639: 3447: 3262: 3238: 3229: 2945: 1720: 1647: 1635: 1611: 1494: 1253: 1207: 1167: 796: 788: 727: 704: 495: 487: 475: 463: 443: 439: 352:

in his seminal paper "The complexity of theorem proving procedures" (and independently by

184: 150: 5215: 4085: 5365: 4404: 1591:

defined a general class of proof techniques for circuit complexity lower bounds, called

5783: 5671: 5593: 5546: 5415: 5342: 4826: 4202:

Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)".

3925: 3225: 2286:{\displaystyle t_{M}(w)={\text{ number of steps }}M{\text{ takes to halt on input }}w.} 2117: 1847:

with unbounded memory) that produces the correct answer for any input string of length

1840: 1660:

These barriers lead some computer scientists to suggest the P versus NP problem may be

1619: 1560: 1364: 1249: 1223: 1158:(time vs. problem size) of such algorithms can be surprisingly low. An example is the 1055: 599: 532: 483: 380: 376: 170: 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

989: 542:

will accept exist? It is in NP because (given an input) it is simple to check whether

5894: 5371: 5294: 5266: 5144: 4585:

Johnson, David S. (August 2012). "A Brief History of NP-Completeness, 1954–2012". In

4507: 4225: 4137: 4101: 3985:

Valiant, Leslie G. (1979). "The complexity of enumeration and reliability problems".

3911: 3839: 3822: 3707: 3402: 2010:

and a deterministic polynomial-time Turing machine is a deterministic Turing machine

1623: 1593: 1588: 1578: 998: 479: 368: 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: 4960: 4627: 4469: 4277: 3531: 3497: 3443: 3191: 1733: 1693: 1669: 1461: 1439: 1325: 1166:, which works surprisingly well in practice; despite having exponential worst-case 564: 353: 349: 205: 4320: 4256: 4240: 4115:

Babai, László (2018). "Group, graphs, algorithms: the graph isomorphism problem".

1485: 1119:{\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))} 4493: 3929: 3643: 3159:

is NP-complete. This is a common way of proving some new problem is NP-complete.

567:

in polynomial time. This in turn gives a solution to the problem of partitioning

5661: 5571: 4986: 4930: 4830: 3651: 3622:

Introduction to the Theory of Computation, Second Edition, International Edition

1267: 1244:

also shows that very simple questions may be settled only by very deep theories.

1031: 384: 213: 193:

solved in polynomial time, but the answer could be verified in polynomial time.

154: 4866: 4389:. Lecture Notes in Computer Science. Vol. 1350. Springer. pp. 22–31. 4187: 4168: 2932:

COMPOSITE also happens to be in P, a fact demonstrated by the invention of the

5773: 5598: 5466: 4792: 4461: 3624:, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20. 1631: 1361: 1351: 435: 235:, each of which carries a US$ 1,000,000 prize for the first correct solution. 217: 17: 5334: 4695: 4613: 4071: 442:

consists of all decision problems whose positive solutions are verifiable in

5768: 5276: 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:

1836: 1643: 1227: 221: 166: 29: 4773: 4756: 348:

The precise statement of the P versus NP problem was introduced in 1971 by

5060: 4545: 4537: 4058:

Arvind, Vikraman; Kurur, Piyush P. (2006). "Graph isomorphism is in SPP".

4035: 4016: 3674: 3513: 5763: 5758: 5703: 5526: 5307:. Series of Books in the Mathematical Sciences (1st ed.). New York: 3854:

I. Holyer (1981). "The NP-completeness of some edge-partition problems".

1442:(assuming not only a proof, but a practically efficient algorithm) says: 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

5035:"'Travelling Salesman' movie considers the repercussions if P equals NP" 5753: 5474: 4939: 4681: 4658:

L. R. Foulds (October 1983). "The Heuristic Problem-Solving Approach".

4343: 1368: 711: 615: 587: 504: 204:, a proof either way would have profound implications for mathematics, 5713: 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

5860: 5855: 5730: 5481: 3604:

Bulletin of the European Association for Theoretical Computer Science

1639: 1615: 244: 5399: 4741: 4673: 4385:

Horie, S.; Watanabe, O. (1997). "Hard instance generation for SAT".

3998: 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.

1490: 287:, is there at least one legal solution where every row, column, and 4395: 1756:// "Polynomial-time" means it returns "yes" in polynomial time when 5850: 5845: 5666: 2638:

is decidable by a deterministic Turing machine in polynomial time.

1203: 1001:

suggests that the algorithmic complexity of the problem is O((log(

792: 628: 474: 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

1170:, it runs on par with the best known polynomial-time algorithms. 450:

machine. Clearly, P ⊆ NP. Arguably, the biggest open question in

5678: 5536: 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". 1288: 1284: 5485: 4272: 4270: 434:) solvable on a deterministic sequential machine in a duration 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,

5693: 5625: 5620: 5541: 5531: 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. 1665: 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

1324:

A solution showing P = NP could upend the field of

791:

algorithm. The integer factorization problem is in NP and in

528:

NP-complete, and no fast algorithm for any of them is known.

5441: 3956:

Proceedings of the SIAM-AMS Symposium in Applied Mathematics

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

243:

Consider the following yes/no problem: given an incomplete

1688:

Consider all languages of finite structures with a fixed

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

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

5838: 5802: 5746: 5639: 5519: 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 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" 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 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, 5117:"Elementary Solve for X Review: Sines of Murder" 4558:History of this letter and its translation from 3551:[Problems of Information Transmission]. 2155: 779:is the computational problem of determining the 5467:"P vs. NP and the Computational Complexity Zoo" 3930:"Computational Complexity of Games and Puzzles" 1466: 1444: 1404: 1379:solutions that do not assume P ≠ NP. 1259: 1237: 1215: 4755:Razborov, Alexander A.; Steven Rudich (1997). 4169:"The disjoint paths problem in quadratic time" 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: 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 1038:is fixed, can be solved in a running time of 111: 8: 4696:"A personal view of average-case complexity" 4163:Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; 3597:"Gödel, von Neumann, and the P = NP problem" 2624: 2618: 2592: 2556: 2221: 2158: 1994: 1961: 1920: 1885: 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) 4661:Journal of the Operational Research Society 4598:. Documenta Mathematica. pp. 359–376. 4010: 4008: 1476:bitwise or addition or shift operations on 421:(it performs actions one after the other). 200:. Aside from being an important problem in 5504: 5490: 5482: 5451:Hardness of Approximation Between P and NP 4245:Advances in linear and integer programming 3244:A similar problem exists in the theory of 1780:// considering that string of bits to be a 118: 104: 47: 5389: 4929: 4772: 4527: 4451: 4394: 4261:at McMaster University website of Terlaky 4215: 4186: 4034: 3838: 3664: 3425: 3363: 3351: 3327: 3315: 3073: 3038: 3024: 3000: 2986: 2888: 2880: 2873: 2854: 2853: 2846: 2845: 2814: 2773: 2754: 2753: 2710: 2708: 2610: 2598:{\displaystyle L_{R}=\{x\#y:(x,y)\in R\}} 2547: 2541: 2512: 2507: 2498: 2484: 2476: 2474: 2441: 2414: 2393: 2381: 2351: 2338: 2326: 2315:be a language over a finite alphabet, Σ. 2272: 2264: 2246: 2240: 2210: 2202: 2193: 2165: 2137: 2131: 2093: 2065: 2059: 2033: 1986: 1974: 1944: 1912: 1877: 1875: 1783:// program. Every possible program can be 1771:// Runs forever with no output otherwise. 1099: 1067: 931: 879: 842: 815: 674: 669: 663: 324: 318: 292: 271: 258: 252: 5139: 5137: 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 1541: 1484: 988: 4949:from the original on 26 September 2006. 4761:Journal of Computer and System Sciences 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" 3407:"The status of the P versus NP problem" 3394: 3289: 1510:P ≠ NP still leaves open the 431: 313:square contains the integers 1 through 50: 5906:Computer-related introductions in 1956 4855:Ben-David, Shai; Halevi, Shai (1992). 4831:"Is P Versus NP Formally Independent?" 4815:from the original on 21 February 2008. 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 4843:from the original on 16 January 2017. 4786: 4784: 4574:from the original on 2 February 2014. 4300:from the original on 16 December 2013 4257:Postscript file at website of Gondzio 3728:from the original on 24 January 2014. 3584:from the original on 9 November 2018. 3278:Unsolved problems in computer science 3205:In the second episode of season 2 of 7: 5115:Kirkpatrick, Noel (4 October 2013). 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 1185:Reasons to believe P ≠ NP or P = NP 5074:Shadia, Ajam (13 September 2013). 4858:On the independence of P versus NP 4791:S. Aaronson; A. Wigderson (2008). 3755:from the original on 31 March 2019 3692:from the original on 15 June 2007. 3353: 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 169:can answer in polynomial time is " 25: 5866:Probabilistically checkable proof 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 5033:Geere, Duncan (26 April 2012). 4174:Journal of Combinatorial Theory 3899:Journal of Combinatorial Theory 3298:nondeterministic Turing machine 2014:that satisfies two conditions: 1664:of standard axiom systems like 1537:computational complexity theory 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). 3375:{\displaystyle \Omega (N^{4})} 3369: 3356: 3333: 3320: 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 1: 4029:: 151–171 See Corollary 1.1. 3821:Colbourn, Charles J. (1984). 3548:Универсальные задачи перебора 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 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 4931:10.4007/annals.2004.160.781 4060:Information and Computation 3137:) on its tape on any input 2266: number of steps 1392:travelling salesman problem 5952: 5882:List of complexity classes 5442:"Computational complexity" 5351:Cambridge University Press 5347:P, NP, and NP-Completeness 5272:Introduction to Algorithms 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: 233:Clay Mathematics Institute 5921:Millennium Prize Problems 5916:Mathematical optimization 5879: 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 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})} 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: 1456:Fermat's Last Theorem 1358:Cryptographic hashing 1242:Fermat's Last Theorem 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: 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: 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: 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: 5439: 5436: 5426: 5406: 5400:10.1137/0216051 5370: 5361: 5343:Goldreich, Oded 5341: 5319: 5293: 5287: 5265: 5262: 5260:Further reading 5245: 5243: 5235: 5226: 5224: 5213: 5201: 5199: 5187: 5184: 5179: 5171:L. G. Valiant. 5170: 5166: 5159: 5143: 5142: 5135: 5125: 5123: 5114: 5113: 5109: 5099: 5097: 5088: 5087: 5083: 5073: 5072: 5068: 5058: 5057: 5053: 5043: 5041: 5032: 5031: 5027: 5017: 5015: 5006: 5005: 5001: 4991: 4989: 4981: 4980: 4976: 4959: 4958: 4954: 4946: 4911: 4906: 4905: 4901: 4892:Wayback Machine 4882: 4878: 4869: 4854: 4853: 4849: 4840: 4833: 4827:Aaronson, Scott 4825: 4824: 4820: 4812: 4797: 4790: 4789: 4782: 4754: 4753: 4749: 4742:10.1137/0204037 4725: 4724: 4720: 4707: 4706: 4702: 4693: 4689: 4674:10.2307/2580891 4668:(10): 927–934. 4657: 4656: 4652: 4642: 4640: 4630:(20 May 2014). 4626: 4625: 4621: 4606: 4595: 4584: 4583: 4579: 4571: 4564: 4559: 4557: 4553: 4529:10.1.1.139.5547 4516:J. Comput. Biol 4506: 4505: 4501: 4483: 4482: 4478: 4437: 4435: 4431: 4423: 4384: 4382: 4378: 4370: 4357: 4356: 4352: 4341: 4340: 4336: 4318: 4317: 4313: 4303: 4301: 4297: 4284: 4276: 4275: 4268: 4238: 4237: 4233: 4217:10.1.1.114.3864 4201: 4200: 4196: 4162: 4161: 4157: 4152: 4148: 4136: 4132: 4114: 4113: 4109: 4084: 4083: 4079: 4057: 4056: 4052: 4014: 4013: 4006: 3999:10.1137/0208032 3984: 3983: 3979: 3969: 3967: 3942: 3941: 3937: 3924: 3923: 3919: 3880: 3879: 3875: 3868:10.1137/0210054 3853: 3852: 3848: 3820: 3819: 3815: 3805: 3803: 3801:www.cs.ox.ac.uk 3795: 3794: 3790: 3780: 3778: 3773: 3772: 3768: 3758: 3756: 3752: 3745: 3741: 3740: 3733: 3725: 3710: 3702: 3701: 3697: 3689: 3666:10.1.1.172.1005 3646: 3638: 3637: 3628: 3619: 3615: 3599: 3594: 3593: 3589: 3581: 3574: 3569: 3568: 3564: 3549: 3544: 3543: 3539: 3524: 3496: 3495: 3491: 3484: 3471: 3470: 3466: 3456: 3454: 3450: 3409: 3401: 3400: 3396: 3392: 3387: 3386: 3359: 3348: 3347: 3323: 3312: 3311: 3309: 3305: 3295: 3291: 3286: 3263:Game complexity 3259: 3221: 3195: 3178: 3176:Popular culture 3165: 3084: 3070: 3069: 3068:in Σ* we have: 3034: 3026: 3021: 3020: 2996: 2988: 2983: 2982: 2948: 2946:NP-completeness 2942: 2940:NP-completeness 2882: and 2826: 2822: 2811: 2810: 2746: 2742: 2705: 2704: 2698: 2647: 2607: 2606: 2543: 2538: 2537: 2506: 2471: 2470: 2437: 2411: 2410: 2389: 2378: 2377: 2347: 2334: 2323: 2322: 2242: 2237: 2236: 2189: 2161: 2133: 2128: 2127: 2089: 2061: 2056: 2055: 2030: 2029: 1970: 1941: 1940: 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 1064: 1063: 1012:Cobham's thesis 987: 895: 891: 890: 845: 841: 837: 836: 835: 831: 824: 820: 812: 811: 730: 728:NP-intermediate 724: 705:halting problem 670: 665: 660: 659: 584: 578: 576:Harder problems 498: 496:NP-completeness 473: 471:NP-completeness 464:William Gasarch 444:polynomial time 393: 346: 320: 315: 314: 289: 288: 267: 254: 249: 248: 241: 151:polynomial time 124: 44: 43: 38: 35: 31: 28: 23: 22: 15: 12: 11: 5: 5949: 5947: 5939: 5938: 5933: 5928: 5923: 5918: 5913: 5908: 5903: 5893: 5892: 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: 5511: 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: 24: 18:P = NP problem 14: 13: 10: 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: 5433: 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: 5259: 5254: 5242: 5238: 5234: 5223: 5222: 5217: 5212: 5209: 5198: 5197: 5191: 5186: 5185: 5181: 5174: 5168: 5165: 5160: 5154: 5150: 5146: 5140: 5138: 5134: 5122: 5118: 5111: 5108: 5096: 5092: 5085: 5082: 5077: 5070: 5067: 5062: 5055: 5052: 5040: 5036: 5029: 5026: 5014: 5010: 5003: 5000: 4988: 4984: 4978: 4975: 4970: 4966: 4962: 4956: 4953: 4945: 4941: 4937: 4932: 4927: 4923: 4919: 4918: 4910: 4903: 4900: 4896: 4893: 4889: 4886: 4885:"P versus NP" 4880: 4877: 4868: 4864: 4860: 4859: 4851: 4848: 4839: 4832: 4828: 4822: 4819: 4811: 4807: 4803: 4796: 4795: 4787: 4785: 4781: 4775: 4770: 4766: 4762: 4758: 4751: 4748: 4743: 4739: 4735: 4731: 4730: 4722: 4719: 4714: 4710: 4704: 4701: 4697: 4691: 4688: 4683: 4679: 4675: 4671: 4667: 4663: 4662: 4654: 4651: 4639: 4635: 4634: 4629: 4623: 4620: 4615: 4611: 4607: 4601: 4594: 4593: 4588: 4587:Grötschel, M. 4581: 4578: 4570: 4563: 4555: 4552: 4547: 4543: 4539: 4535: 4530: 4525: 4521: 4517: 4513: 4509: 4503: 4500: 4495: 4491: 4487: 4480: 4477: 4471: 4467: 4463: 4459: 4454: 4449: 4445: 4441: 4433: 4430: 4424: 4418: 4414: 4410: 4406: 4402: 4397: 4392: 4388: 4380: 4377: 4374:, Theorem 3.9 4371: 4369:3-540-52079-1 4365: 4361: 4354: 4351: 4345: 4338: 4335: 4330: 4326: 4322: 4315: 4312: 4296: 4292: 4291: 4283: 4279: 4278:Cook, Stephen 4273: 4271: 4267: 4262: 4258: 4254: 4250: 4246: 4242: 4235: 4232: 4227: 4223: 4218: 4213: 4209: 4205: 4198: 4195: 4189: 4184: 4180: 4176: 4175: 4170: 4166: 4159: 4156: 4150: 4147: 4143: 4139: 4138:Lance Fortnow 4134: 4131: 4126: 4122: 4118: 4111: 4108: 4103: 4099: 4095: 4091: 4087: 4086:Schöning, Uwe 4081: 4078: 4073: 4069: 4065: 4061: 4054: 4051: 4046: 4042: 4037: 4032: 4028: 4024: 4023: 4018: 4011: 4009: 4005: 4000: 3996: 3992: 3988: 3981: 3978: 3965: 3961: 3957: 3953: 3949: 3945: 3939: 3936: 3931: 3927: 3921: 3918: 3913: 3909: 3905: 3901: 3900: 3895: 3891: 3887: 3883: 3877: 3874: 3869: 3865: 3861: 3857: 3850: 3847: 3841: 3836: 3832: 3828: 3824: 3817: 3814: 3802: 3798: 3792: 3789: 3777: 3770: 3767: 3751: 3744: 3738: 3736: 3732: 3724: 3720: 3716: 3709: 3705: 3699: 3696: 3688: 3684: 3680: 3676: 3672: 3667: 3662: 3658: 3654: 3653: 3645: 3642:(June 2002). 3641: 3635: 3633: 3631: 3627: 3623: 3617: 3614: 3609: 3605: 3598: 3591: 3588: 3580: 3573: 3566: 3563: 3559:(3): 115–116. 3558: 3554: 3550: 3541: 3538: 3533: 3529: 3525: 3523:9781450374644 3519: 3515: 3511: 3507: 3503: 3499: 3498:Cook, Stephen 3493: 3490: 3485: 3483:9780691156491 3479: 3475: 3468: 3465: 3449: 3445: 3441: 3437: 3433: 3428: 3423: 3419: 3415: 3408: 3404: 3398: 3395: 3389: 3364: 3360: 3328: 3324: 3317: 3307: 3304: 3299: 3293: 3290: 3283: 3279: 3276: 3274: 3271: 3269: 3266: 3264: 3261: 3260: 3256: 3251: 3247: 3243: 3240: 3236: 3232: 3231: 3227: 3223: 3222: 3218: 3216: 3214: 3213:"Solve for X" 3210: 3209: 3203: 3201: 3194: 3193: 3187: 3185: 3184: 3175: 3173: 3170: 3162: 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: 2939: 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: 2695: 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: 1819: 1814: 1812: 1806: 1801: 1799: 1790: 1787: 1784: 1781: 1778: 1775: 1772: 1769: 1766: 1763: 1760: 1757: 1754: 1751: 1748: 1745: 1741: 1739: 1735: 1726: 1724: 1722: 1718: 1714: 1710: 1705: 1703: 1699: 1695: 1691: 1686: 1684: 1676: 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: 1526: 1524: 1522: 1517: 1513: 1508: 1501: 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: 1303: 1301: 1294: 1292: 1290: 1286: 1278: 1273: 1269: 1263: 1255: 1251: 1245: 1243: 1236: 1229: 1225: 1219: 1214: 1211: 1209: 1205: 1201: 1197: 1192: 1184: 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: 984: 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: 721: 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: 575: 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: 470: 468: 465: 457: 456: 455: 453: 449: 445: 441: 437: 433: 429: 428: 422: 420: 416: 415: 414:deterministic 409: 406: 402: 398: 390: 388: 386: 382: 378: 374: 370: 366: 362: 357: 355: 351: 343: 341: 325: 321: 300: 297: 294: 272: 268: 264: 259: 255: 247:grid of size 246: 238: 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: 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 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.

Index