Claims
Search the graph by meaning. Each result carries its current verdict; open one to see its decomposition, provenance, and the reasoning behind the assessment.
KindShowingImportancePrizesTopicP versus NP problem
The open problem in computational complexity theory, due to Cook and Levin, asking whether P — the class of decision problems solvable in polynomial time — equals NP, the class whose proposed solutions are verifiable in polynomial time. Claims about whether P equals NP, purported proofs or disproofs, proof barriers, and consequences of either resolution belong here.
Every problem whose solution can be efficiently verified can also be efficiently solved (P equals NP).
UnknownInsufficient information to assess.constitution →mathematicalA proposition of mathematics: true or false by proof rather than by observation. Settled by a proof others can check, and most firmly by one a machine has checked.constitution →Computational complexity theoryimportance · majorImportance 0.80, from 0 to 1 · major: real consequence within a domain, actively argued. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →
Stephen Cook and Leonid Levin independently formulated the P versus NP problem in 1971.
SupportedThe evidence favors the claim, but the examination is incomplete or the evidence is indirect.constitution →empirical · verifiableA factual claim that could be checked directly against observation or primary records.constitution →Computational complexity theoryimportance · settledImportance 0.15, from 0 to 1 · settled: uncontested, so low even when much depends on it. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →
Cook's 1971 paper introduced NP-completeness and posed the P versus NP question.
UnassessedNo current assessment. Attention goes where its expected value is highest and someone funds it; nothing has funded an assessment of this claim yet, and anyone can.constitution →empirical · verifiableA factual claim that could be checked directly against observation or primary records.constitution →Computational complexity theoryNP-complete problemsimportance · settledImportance 0.12, from 0 to 1 · settled: uncontested, so low even when much depends on it. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →
No claimed proof that P equals NP or that P differs from NP has withstood expert scrutiny.
UnassessedNo current assessment. Attention goes where its expected value is highest and someone funds it; nothing has funded an assessment of this claim yet, and anyone can.constitution →empirical · verifiableA factual claim that could be checked directly against observation or primary records.constitution →Computational complexity theoryimportance · settledImportance 0.20, from 0 to 1 · settled: uncontested, so low even when much depends on it. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →
Relativizing, natural, and algebrizing proof techniques cannot resolve whether P equals NP.
UnassessedNo current assessment. Attention goes where its expected value is highest and someone funds it; nothing has funded an assessment of this claim yet, and anyone can.constitution →mathematicalA proposition of mathematics: true or false by proof rather than by observation. Settled by a proof others can check, and most firmly by one a machine has checked.constitution →Computational complexity theoryComplexity-theoretic proof barriersimportance · minorImportance 0.30, from 0 to 1 · minor: narrow or largely settled, cheap to get right. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →
If P equals NP, the polynomial hierarchy collapses to P.
UnassessedNo current assessment. Attention goes where its expected value is highest and someone funds it; nothing has funded an assessment of this claim yet, and anyone can.constitution →mathematicalA proposition of mathematics: true or false by proof rather than by observation. Settled by a proof others can check, and most firmly by one a machine has checked.constitution →Computational complexity theoryPolynomial hierarchyimportance · settledImportance 0.12, from 0 to 1 · settled: uncontested, so low even when much depends on it. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →
No polynomial-time algorithm is known for any NP-complete problem.
UnassessedNo current assessment. Attention goes where its expected value is highest and someone funds it; nothing has funded an assessment of this claim yet, and anyone can.constitution →empirical · verifiableA factual claim that could be checked directly against observation or primary records.constitution →Computational complexity theoryNP-complete problemsimportance · settledImportance 0.15, from 0 to 1 · settled: uncontested, so low even when much depends on it. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →
Most theoretical computer scientists believe that P is not equal to NP.
UnassessedNo current assessment. Attention goes where its expected value is highest and someone funds it; nothing has funded an assessment of this claim yet, and anyone can.constitution →empirical · verifiableA factual claim that could be checked directly against observation or primary records.constitution →Computational complexity theoryExpert opinion surveysimportance · minorImportance 0.25, from 0 to 1 · minor: narrow or largely settled, cheap to get right. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →
Contribute
If a claim here is wrong, or missing evidence, open it: every claim page carries its own entry for challenges, evidence, and corrections. If the graph is missing a claim or a question entirely, propose it below. A proposal is reviewed on its wording; accepted proposals are matched against the graph before they enter it.