Editing P versus NP problem (section)

==Reasons to believe P ≠ NP or P = NP==
Cook provides a restatement of the problem in ''The P Versus NP Problem'' as "Does P&nbsp;=&nbsp;NP?"<ref name="Official Problem Description"/> According to polls,<ref name="poll"/><ref>{{cite journal |title=P vs. NP poll results |journal=Communications of the ACM |date=May 2012 |volume=55 |issue=5 |page=10 |first= Jack|last=Rosenberger |url=http://mags.acm.org/communications/201205?pg=12}}</ref> most computer scientists believe that P&nbsp;≠&nbsp;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 3,000 important known NP-complete problems (see [[List of NP-complete problems]]). These algorithms were sought long before the concept of NP-completeness was even defined ([[Karp's 21 NP-complete problems]], among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P&nbsp;=&nbsp;NP would imply many other startling results that are currently believed to be false, such as NP&nbsp;=&nbsp;[[co-NP]] and P&nbsp;=&nbsp;[[PH (complexity)|PH]].

It is also intuitively argued that the existence of problems that are hard to solve but whose solutions are easy to verify matches real-world experience.<ref>{{Cite web |url=http://scottaaronson.com/blog/?p=122 |author=Scott Aaronson |title=Reasons to believe |date=4 September 2006 }}, point 9.</ref>
{{Blockquote|If P <nowiki>=</nowiki> 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 found.| [[Scott Aaronson]], [[UT Austin]]}}

On the other hand, some researchers believe that it is overconfident to believe P&nbsp;≠&nbsp;NP and that researchers should also explore proofs of P&nbsp;=&nbsp;NP. For example, in 2002 these statements were made:<ref name="poll" />
{{Blockquote|The main argument in favor of P&nbsp;≠&nbsp;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 [[Fermat's Last Theorem]] also shows that very simple questions may be settled only by very deep theories.|[[Moshe Y. Vardi]], [[Rice University]]}}
{{quote|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 methods required.|[[Anil Nerode]], [[Cornell University]]}}

===DLIN vs NLIN===
When one substitutes "linear time on a multitape Turing machine" for "polynomial time" in the definitions of P and NP, one obtains the classes [[DLIN]] and [[NLIN]].
It is known<ref>{{cite book |last1=Balcazar |first1=Jose Luis |last2=Diaz |first2=Josep |last3=Gabarro |first3=Joaquim |title=Structural Complexity II |date=1990 |publisher=Springer Verlag |isbn=3-540-52079-1}}, Theorem 3.9</ref> that DLIN ≠ NLIN.