Editing P versus NP problem (section)

==Results about difficulty of proof==
Although the P&nbsp;=&nbsp;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&nbsp;=&nbsp;NP problem has been in showing that existing proof techniques are insufficient for answering the question, suggesting novel technical approaches are required.

As additional evidence for the difficulty of the problem, essentially all known proof techniques in [[computational complexity theory]] fall into one of the following classifications, all insufficient to prove P&nbsp;≠&nbsp;NP:
{| class="wikitable"
|-
!Classification
!Definition
|-
|[[Relativizing proof]]s
|Imagine a world where every algorithm is allowed to make queries to some fixed subroutine called an ''[[oracle machine|oracle]]'' (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 ''relativizing''. In 1975, Baker, Gill, and [[Robert M. Solovay|Solovay]] showed that P&nbsp;=&nbsp;NP with respect to some oracles, while P&nbsp;≠&nbsp;NP for other oracles.<ref>{{cite journal |author1=T. P. Baker |author2=J. Gill |author3=R. Solovay |title=Relativizations of the P =? NP Question |journal=[[SIAM Journal on Computing]] |volume=4 |issue=4 |pages=431–442 |year=1975 |doi=10.1137/0204037}}</ref> As relativizing proofs can only prove statements that are true for all possible oracles, these techniques cannot resolve P&nbsp;=&nbsp;NP.
|-
|[[Natural proof]]s
|In 1993, [[Alexander Razborov]] and [[Steven Rudich]] defined a general class of proof techniques for circuit complexity lower bounds, called ''[[natural proof]]s''.<ref>{{cite journal |author1=Razborov, Alexander A. |author2=Steven Rudich |title=Natural proofs |journal=Journal of Computer and System Sciences |volume=55 |issue=1 |year=1997 |pages=24–35 |doi=10.1006/jcss.1997.1494 |doi-access=free }}</ref> At the time, all previously known circuit lower bounds were natural, and circuit complexity was considered a very promising approach for resolving P&nbsp;=&nbsp;NP. However, Razborov and Rudich showed that if [[one-way functions]] 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&nbsp;≠&nbsp;NP. Thus it is unlikely that natural proofs alone can resolve P&nbsp;=&nbsp;NP.
|-
|Algebrizing proofs
|After the Baker–Gill–Solovay result, new non-relativizing proof techniques were successfully used to prove that [[IP (complexity)|IP]]&nbsp;=&nbsp;[[PSPACE]]. However, in 2008, [[Scott Aaronson]] and [[Avi Wigderson]] showed that the main technical tool used in the IP&nbsp;=&nbsp;PSPACE proof, known as ''arithmetization'', was also insufficient to resolve P&nbsp;=&nbsp;NP.<ref name=":0">{{cite conference |author1=S. Aaronson |author2=A. Wigderson |title=Algebrization: A New Barrier in Complexity Theory |conference=Proceedings of ACM STOC'2008 |year=2008 |url=http://www.scottaaronson.com/papers/alg.pdf |archive-url=https://web.archive.org/web/20080221223917/http://www.scottaaronson.com/papers/alg.pdf |archive-date=2008-02-21 |url-status=live |doi=10.1145/1374376.1374481 |pages=731–740}}</ref> Arithmetization converts the operations of an algorithm to algebraic and basic [[arithmetic]] symbols and then uses those to analyze the workings. In the  [[IP (complexity)|IP]]&nbsp;=&nbsp;[[PSPACE]] proof, they convert the [[black box]] and the Boolean circuits to an algebraic problem.<ref name=":0" /> As mentioned previously, it has been proven that this method is not viable to solve P&nbsp;=&nbsp;NP and other [[time complexity]] problems.
|}

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&nbsp;=&nbsp;NP problem in a way not excluded by the above results.

These barriers lead some computer scientists to suggest the P versus NP problem may be [[Independence (mathematical logic)|independent]] of standard axiom systems like [[ZFC]] (cannot be proved or disproved within them). An independence result could imply that either P&nbsp;≠&nbsp;NP and this is unprovable in (e.g.) ZFC, or that P&nbsp;=&nbsp;NP but it is unprovable in ZFC that any polynomial-time algorithms are correct.<ref>{{Cite web |url=http://www.scottaaronson.com/papers/indep.pdf |archive-url=https://web.archive.org/web/20170116143825/http://www.scottaaronson.com/papers/indep.pdf |archive-date=2017-01-16 |url-status=live |first=Scott |last=Aaronson |author-link=Scott Aaronson |title=Is P Versus NP Formally Independent?}}.</ref> However, if the problem is undecidable even with much weaker assumptions extending the [[Peano axioms]] for integer arithmetic, then nearly polynomial-time algorithms exist for all NP problems.<ref>{{Cite tech report |title=On the independence of P versus NP |first1=Shai |last1=Ben-David |first2=Shai |last2=Halevi |volume=714 |website=Technion |year=1992 |url=https://www.cs.technion.ac.il/~shai/ph.ps.gz |format=GZIP |archive-url=https://web.archive.org/web/20120302072225/https://www.cs.technion.ac.il/~shai/ph.ps.gz |archive-date=2012-03-02}}.</ref> 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 or ZFC with current techniques is no easier than proving all NP problems have efficient algorithms.