Source labels openMillennium Problems · Computer science
Conjectures in Complexity Theory
P ≠ NP*:
The conjecture that the complexity classes P and NP are not equal.
Source checked Jul 26, 20261 pinned Lean statementInspect problem
Questions, not proof records
Open-problem statements, with their sources attached.
Each statement record keeps the mathematical question, a dated status source, accessible references, and any pinned Lean formulation separate from proof verification.
“Open” is a dated source assertion. In these pinned sources,
sorry marks an admitted statement, not a proof. Source indexing does not mean the formulation has been independently built or certified by Therefore.Source labels openMillennium Problems · Computer science
Conjectures in Complexity Theory
NP ≠ coNP*:
The conjecture that the complexity classes NP and coNP are not equal.
Source checked Jul 26, 20261 pinned Lean statementInspect problem
Source labels openPapers · Computer science
Strong Sensitivity Conjecture (`bs(f) ≤ s(f)^2`)
Strong Sensitivity Conjecture,
for every Boolean function f : {0,1}^n → {0,1},
bs(f) ≤ s(f)^2.
We call this the strong sensitivity conjecture because the original sensitivity
conjecture only asked for a polynomial bound in terms of s(f). Huang's
celebrated result (often called the sensitivity theorem) gives a quartic bound,
bs(f) ≤ s(f)^4, thereby settling the original conjecture.
Source checked Jul 26, 20261 pinned Lean statementInspect problem
Source labels openWikipedia · Computer science
Černý Conjecture
Černý Conjecture*: Every synchronizing DFA with states admits a synchronizing word of length at most .
Source checked Jul 26, 20261 pinned Lean statementInspect problem