Editing P versus NP problem (section)

==Context==
The relation between the [[complexity class]]es P and NP is studied in [[computational complexity theory]], the part of the [[theory of computation]] 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).

In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is ''[[Deterministic computation|deterministic]]'' (given the computer's present state and any inputs, there is only one possible action that the computer might take) and ''sequential'' (it performs actions one after the other).

In this theory, the class P consists of all ''[[decision problem]]s'' (defined [[#Formal definitions|below]]) solvable on a deterministic sequential machine in a duration [[polynomial]] in the size of the input; the class [[NP (complexity)|NP]] consists of all decision problems whose positive solutions are verifiable in [[polynomial time]] given the right information, or equivalently, whose solution can be found in polynomial time on a [[Non-deterministic Turing machine|non-deterministic]] machine.<ref>Sipser, Michael: ''Introduction to the Theory of Computation, Second Edition, International Edition'', page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.</ref> Clearly, P ⊆ NP. Arguably, the biggest open question in [[theoretical computer science]] concerns the relationship between those two classes:
:Is P equal to NP?

Since 2002, [[William Gasarch]] has conducted three polls of researchers concerning this and related questions.<ref name="poll">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The P=?NP poll.|journal=[[SIGACT News]]|volume=33|issue=2|pages=34–47|date=June 2002| url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |archive-url=https://web.archive.org/web/20070615132837/http://www.cs.umd.edu/~gasarch/papers/poll.pdf |archive-date=2007-06-15 |url-status=live|doi=10.1145/564585.564599| citeseerx=10.1.1.172.1005 | s2cid=36828694 }}</ref><ref name="poll2">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The Second P=?NP poll|journal=SIGACT News|volume=74|url=http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf |archive-url=https://web.archive.org/web/20140124031930/http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf |archive-date=2014-01-24 |url-status=live}}</ref><ref name="poll3">{{Cite web|url=https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf |archive-url=https://web.archive.org/web/20190331023850/https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf |archive-date=2019-03-31 |url-status=live|title=Guest Column: The Third P =? NP Poll1|access-date=25 May 2020}}</ref> Confidence that P&nbsp;≠&nbsp;NP has been increasing – in 2019, 88% believed P&nbsp;≠&nbsp;NP, as opposed to 83% in 2012 and 61% in 2002. When restricted to experts, the 2019 answers became 99% believed P&nbsp;≠&nbsp;NP.<ref name="poll3" /> These polls do not imply whether P&nbsp;=&nbsp;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."