Browse
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.
ShowingImportancePrizesTopicComputational complexity theory
The field at the intersection of mathematics and computer science studying the resources (time, space) required to solve computational problems and the relationships among complexity classes such as P, NP, and PSPACE. Claims about class separations, hardness assumptions, and complexity-theoretic barriers belong here; claims about a specific named open problem should also carry that problem's tag.
Stephen Cook and Leonid Levin independently formulated the P versus NP problem in 1971.
SupportedEvidence favors the claim, but the chain is incomplete or the sources are secondary.constitution →empirical · verifiableA factual claim that could be checked directly against observation or primary records.constitution →P versus NP problemimportance · 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 →P versus NP problemNP-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 →
Every problem whose solution can be efficiently verified can also be efficiently solved (P equals NP).
UnsupportedNo credible evidence found, though the claim is not contradicted.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 →P versus NP problemimportance · 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 →
Cryptographic one-way functions exist.
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 →One-way functionsimportance · minorImportance 0.35, 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 →
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 →P versus NP problemimportance · 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 →P versus NP problemComplexity-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 →P versus NP problemPolynomial 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 →NP-complete problemsP versus NP problemimportance · 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 →P versus NP problemExpert 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 →
Boolean satisfiability is NP-complete.
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 →NP-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 →
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 entirely, propose it below. A proposal is reviewed on its merits; accepted claims are matched against the graph and enter it with their reasoning on record.