Open problems in complexity theory

104 open problems, reduction-shaped and each anchored to a published record. Beat the number on any of them and you have a publishable result. Records are community-maintained; corrections are contributions.

The loop-capable spine (51)

Problems with a published path from their record to an unconditional result — a collision with a hierarchy theorem, the algorithmic method, or hardness magnification. Progress here provably accumulates toward separations.

Derandomize PIT one class up: blackbox identity testing for constant-depth circuits is subexponential, poly-time stops at depth-3 bounded top fan-in — full derandomization triggers the Kabanets–Impagliazzo loop

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10derandomizationpithitting-setsarithmetic-circuitskabanets-impagliazzo

⟳ the fully published algorithm-to-lower-bound loop: PIT ∈ P implies NEXP ⊄ P/poly or the Permanent has no polynomial-size arithmetic circuits (Kabanets & Impagliazzo, comput. complexity 13, 2004); the loop is short-circuited at low depth — a polynomial-size hitting set for depth-4 circuits yields a quasipolynomial hitting set for all of VP (Agrawal & Vinay, FOCS 2008)

Derandomize BPL in space o(log^{3/2} n / sqrt(log log n)) — the Saks–Zhou exponent 3/2 has moved once, subpolynomially, since 1995

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10space-complexityderandomizationbplpseudorandomnesssaks-zhou

⟳ already unconditional — any exponent improvement is a new theorem; a published halfway target exists: a WPRG with seed length O(log^2 n + log(w/ε)) computable in small space yields BPL ⊆ DSPACE(log^{4/3} n) (Braverman, Cohen & Garg, SICOMP 2020; Chattopadhyay & Liao, CCC 2020)

Compute the chromatic number in O((2-ε)^n) time — break the 2^n inclusion-exclusion barrier

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10graphscoloringinclusion-exclusionsubset-convolutionexponential-time

⟳ no path from the algorithm side; conversely, any 2^{n-o(n)} lower bound for chromatic number would unconditionally refute Strassen's asymptotic rank conjecture, which implies a deterministic O(1.99982^n) algorithm (Björklund, Curticapean, Husfeldt, Kaski & Pratt, SODA 2025)

Extend the nontrivial-SAT frontier past ACC0∘THR: a 2^n/n^{ω(1)}-time SAT or CAPP algorithm for poly-size depth-3 TC0 would give NQP ⊄ TC0 by the algorithmic method

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10circuit-complexityalgorithmic-methodsat-algorithmstc0derandomization

⟳ nontrivial SAT gives standard Williams-style lower bounds; for CAPP, the needed error and closure depend on the conversion theorem (constant/o(1) error suffices for the Chen–Williams/Bathie–Williams same-class PCPP bridge, while Chen–Ren's MAJ^3 bridge requires inverse-circuit-size error for every polynomial size); Chen–Tal–Wang's E^NP ⊄ THR∘THR[n^{2.5−ε}] (STOC 2026) is the live template

Directed st-connectivity in o(log^2 n) space — Savitch's 1970 bound is still the record, while the undirected case fell all the way to L

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10space-complexityreachabilitynlsavitchquantum-logspace

⟳ already unconditional — via NL-completeness any o(log^2 n) algorithm improves Savitch's theorem wholesale, and the precedent is published: undirected reachability descended log^{3/2} → log^{4/3} → log n log log n → O(log n), ending at SL = L (Reingold, JACM 2008)

Dynamic time warping is stuck at O(n^2 / log log n)-type bounds — catch up to edit distance's log^2 shaving, or explain why not

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10sequencestime-seriesfine-grainedsethlog-shaving

⟳ shaving all polylog factors from DTW (even 1D curves) implies NTIME[2^O(n)] lacks non-uniform NC^1 circuits — DTW admits the alignment gadgets that simulate branching programs (Abboud-Hansen-Vassilevska Williams-Williams, STOC 2016, Thm 6 + Lemma 6)

Beat O(n^2 / log^2 n) for edit distance, or shave a third log factor — the 46-year-old record vs the SETH quadratic wall

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10stringsfine-grainedsethfour-russianslog-shaving

⟳ shaving all polylogs — O(n^2/log^c n) for every c — implies NTIME[2^O(n)] lacks non-uniform NC^1 circuits; even a specific log^1000 n shave already gives new formula lower bounds (Abboud-Hansen-Vassilevska Williams-Williams, STOC 2016, Cor. 2)

Get a (1+eps)-approximation for edit distance in truly subquadratic time — constants are near-linear since 2020, and STOC 2026 got a PTAS to n^2 / 2^{log^{Omega(1)} n}

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10stringsapproximationedit-distancefine-grainedsethptas

⟳ deterministic route only: a deterministic truly subquadratic (1+1/polylog n)-approximation for edit distance (binary) implies E^NP lacks non-uniform NC^1 circuits (Abboud & Backurs, ITCS 2017, Sec. 4.1 + Thm 27); the constant-factor analogue is published only for LCS (Abboud & Rubinstein, ITCS 2018); nothing known for randomized algorithms

Beat the trivial 1/|alphabet| approximation for LCS in truly subquadratic time — the general-alphabet record is an n^{0.4} factor in linear time

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10stringsapproximationlcsfine-grainedseth

⟳ deterministic route only: a deterministic truly subquadratic (1+o(1))-approximation over alphabet n^{o(1)} implies E^NP lacks non-uniform linear-size Valiant series-parallel circuits (Abboud & Backurs, ITCS 2017, Thm 5); strengthened to super-constant approximation factors and linear-size NC^1 lower bounds via Distributed PCP (Abboud & Rubinstein, ITCS 2018); nothing known for randomized algorithms

Beat O(n^2 / log^2 n) for Longest Common Subsequence — SETH says no n^{2-eps}, circuits say polylog shaving is already big

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10stringsfine-grainedsethlcslog-shaving

⟳ shaving all polylogs — O(n^2/log^c n) for every c, even on binary sequences — implies NTIME[2^O(n)] lacks non-uniform NC^1 circuits; a log^1000 n shave already gives new formula lower bounds (Abboud-Hansen-Vassilevska Williams-Williams, STOC 2016, Cor. 2)

Log-rank conjecture: beat Sudakov–Tomon's O(√rank) deterministic protocol, or push the separation past Ω̃(log² rank)

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10communication-complexitylog-rankrankliftingbarriers

⟳ separation side is on the unconditional loop: deterministic communication lower bounds need no conjectures, so any ω̃((log rank)^2) example is itself a new unconditional result beating Göös-Pitassi-Watson (FOCS 2015); no published unconditional consequence from improving the O(√rank) protocol

Solve Range Avoidance in FP^NP: the record is a single-valued FS2P algorithm working on all input lengths — an FP^NP algorithm would make E^NP near-maximally hard, since Avoid is the hardest explicit construction

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10range-avoidanceexplicit-constructionscircuit-complexitytfnpmeta-complexity

⟳ constructing hard truth tables is complete for APEPP under P^NP reductions, so Avoid ∈ FP^NP yields a function in E^NP of near-maximum circuit complexity 2^n/(2n) — and every probabilistic-method construction (Ramsey graphs, rigid matrices, two-source extractors, hard truth tables) reduces to Avoid (Korten, FOCS 2021, arXiv:2106.00875)

Regular expression matching: beat the ~O(nm / log^{1.5} n) record, with SETH forbidding (nm)^{1-eps}

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10stringsregexfine-grainedsethlog-shaving

⟳ log-shaving is loop-shaped: an O(n^2/log^{7+eps} n) regex-matching algorithm implies new Formula-SAT algorithms, and shaving an arbitrarily large polylog implies NEXP ⊄ NC^1 via the algorithmic method (Abboud & Bringmann, ICALP 2018, arXiv:1804.08978); a truly sub-(nm) algorithm would refute SETH and give E^NP series-parallel circuit lower bounds (Jahanjou–Miles–Viola, ICALP 2015)

Break Nisan's log-squared barrier: a PRG for read-once branching programs with seed o(log^2 n) — unbeaten since 1990

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10pseudorandomnessbranching-programsspace-complexityprgderandomization

⟳ already unconditional — seed o(log^2 n) even for constant width would be the first advance in 35 years, and seed O(log^{3/2} n)-type PRGs feed the Saks–Zhou/Armoni machinery to improve the unconditional BPL ⊆ DSPACE(log^{3/2} n / sqrt(log log n)) record (Saks & Zhou, JCSS 1999; Hoza, RANDOM 2021); Cheng & Hoza (Theory of Computing 2022) reduce breaking the barrier to optimal arity + error dependence

Beat PPSZ's Θ(1/k) savings for k-SAT — solve k-SAT in 2^{n(1 - ω(1/k))} time

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10satexponential-timesethppszsavings

⟳ no direct implication published (Vyas & Williams, SAT 2019, prove none), but one published route is two-for-one: optimal bounds for the local-enumeration problem Enum(k,t) would simultaneously beat PPSZ savings (k-SAT in 2^{n(1-Ω(log k/k))}) and give 2^{ω(sqrt n)} depth-3 circuit lower bounds (Gurumukhani, Paturi, Pudlák, Saks & Talebanfard, CCC 2024, arXiv:2403.09134)

Put Tree Evaluation in O(log n) space, beating the Cook–Mertz O(log n · log log n) bound

open⟳ loop-capableImprove an algorithmconfidence: highverified 2026-08-10space-complexitytree-evaluationcatalyticlogspace

⟳ both directions hit unconditional results: TreeEval in L flows through Williams' simulation (STOC 2025) to give TIME[t] ⊆ SPACE[O(sqrt t)], sharpening the unconditional SPACE[n] ⊄ TIME[n^{2-eps}] separation obtained via the space hierarchy theorem; conversely any ω(log n) space lower bound would prove L ≠ P, since TreeEval is in P (Cook–McKenzie–Wehr–Braverman–Santhanam, TOCT 2012)

Prove any superpolynomial lower bound for AC0[p]-Frege — the circuit analogue fell to Razborov–Smolensky in 1987, the proof-system version has resisted for four decades

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10proof-complexityfregeac0pres-paritynp-vs-conp

⟳ Cook–Reckhow, J. Symbolic Logic 44(1), 1979: superpolynomial lower bounds for every propositional proof system ⟺ NP ≠ coNP; AC0[p]-Frege is the weakest natural system on Cook's program with no superpolynomial bound, so any such bound is unconditional and is the program's next rung

Push the ACC0 lower-bound frontier below NQP: the record separations are NQP ⊄ ACC0 and sub-half-exponential bounds for NEXP — NP ⊄ ACC0 is wide open

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexityacc0algorithmic-methodderandomizationlower-bounds

⟳ already unconditional — any improvement (NP ⊄ ACC0, a bigger NEXP size bound, or NEXP ⊄ TC0) is itself a new unconditional separation, produced via the algorithmic method (Williams, JACM 2014; Murray & Williams, SICOMP 2020)

Pin down the exact entry-size threshold for fast attention: n^{1+o(1)} algorithms at B = o(sqrt(log n)) vs SETH-hardness at B = Theta(sqrt(log n)) — close the constant-factor window and extend it to relative error

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10machine-learningtransformersfine-grainedsethhardness-transfer

⟳ an n^{2-delta} algorithm at B = Theta(sqrt(log n)) would refute SETH (Alman & Song, NeurIPS 2023), and refuting SETH implies E^NP lacks linear-size series-parallel circuits (Jahanjou, Miles & Viola, \"Local Reductions\", Inf. & Comput. 2018)

Prove a (3.1+eps)n circuit lower bound over the full binary basis — the explicit-function record has moved 0.1n in 38 years

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexitygate-eliminationlower-boundsboolean-circuits

⟳ already unconditional — any constant past 3.1 is itself a new lower bound; via hardness magnification, an N^{1+eps} general-circuit lower bound for Gap-MCSP would imply NP ⊄ Circuit[poly] (Oliveira, Pich & Santhanam, CCC 2019; cf. McKay, Murray & Williams, STOC 2019)

Beat Nechiporuk: Ω(n²/log²n) has been the size record for general branching programs since 1966 — and the magnification threshold sits at n^{2+ε}

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexitybranching-programsspace-complexitynechiporuklower-bounds

⟳ polynomial-size branching programs equal nonuniform logspace, so superpolynomial BP bounds for a function in P give P ⊄ L/poly; the published bridge just past the record: Gap-MKtP ∉ BP[N^{2+ε}] implies EXP ⊄ BP[poly] (Oliveira, Pich & Santhanam, CCC 2019, ECCC TR18-158), and any 2^{n^β}-sparse NP language outside BP[n^{2+ε}] implies NP ⊄ BP[n^k] for all k (Chen, Jin & Williams, FOCS 2019, ECCC TR19-118) — Nechiporuk's n²/log²n sits a log²·n^ε factor below that threshold

Raise the constant-depth arithmetic exponent: the record for product-depth Δ is n^{Ω(d^{1/(φ²)^Δ})} — reaching n^{ω(√d)} at depth 4 separates VP from VNP

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10arithmetic-circuitsconstant-depthdepth-reductionvp-vs-vnpset-multilinear

⟳ the published depth-reduction escalator: every polynomial in VP has homogeneous ΣΠΣΠ circuits with bottom fan-in O(√d) and size n^{O(√d)}, so an explicit degree-d polynomial requiring such depth-4 circuits of size n^{ω(√d)} implies VP ≠ VNP (Agrawal & Vinay, FOCS 2008; Koiran, Theoret. Comput. Sci. 448, 2012; Tavenas, Inf. Comput. 240, 2015); over characteristic 0, strong enough depth-3 bounds suffice (Gupta–Kamath–Kayal–Saptharishi, FOCS 2013 / SICOMP 2016)

Break the cubic barrier for de Morgan formulas: the record is n^{3−o(1)} (Håstad, tightened by Tal) and n^{3+eps} needs a new technique

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10formula-complexityshrinkagekrwandreevde-morgan

⟳ already unconditional — any super-cubic bound is itself new; magnification sits exactly at this barrier: an N^{3+eps} de Morgan formula lower bound for Gap-MKtP implies EXP ⊄ NC1 (Oliveira, Pich & Santhanam, CCC 2019)

Depth-3 circuits: beat 2^{1.282√n} — no explicit function has a 2^{ω(√n)} bound, and Majority via local enumeration is the published route

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexitydepth-3satppszlower-bounds

⟳ already unconditional — any constant above 1.282 is a new record; optimal bounds for the local-enumeration problem Enum(k,t) would give a 2^{ω(√n)} unrestricted depth-3 lower bound for Majority, simultaneously improving k-SAT savings to Θ(log k/k) (Gurumukhani et al., CCC 2024, arXiv:2403.09134 — the same two-for-one cited in super-strong-eth-ksat-savings); further out, a 2^{ω(n/log log n)} Σ₃ bound for an explicit function implies super-linear lower bounds for log-depth circuits via Valiant's depth reduction (Valiant, MFCS 1977)

Beat Ω̃((log n / log log n)^2) — the highest unconditional cell-probe lower bound for any dynamic problem

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10cell-probelower-boundsdynamicmultiphase3sumbarriers

⟳ on the unconditional loop by definition: the record IS an unconditional cell-probe lower bound, so any improvement is itself a new unconditional result (Larsen, STOC 2012; Larsen-Weinstein-Yu, STOC 2018; Larsen-Yu, FOCS 2023)

Exactly-N and the corners problem: close the gap between the new (log N)^Ω(1) NOF lower bound and the √(log N) Behrend protocol

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10communication-complexitynofcornersexactly-nadditive-combinatorics

⟳ on the unconditional loop: NOF communication bounds need no conjectures, so any improvement is itself a new unconditional result; scaling Exactly-N lower bounds to superpolylog cost for polylog-many players would give ACC^0 circuit lower bounds via the Yao/Beigel-Tarui SYM-of-AND collapse plus Håstad-Goldmann's NOF protocols (Comput. Complexity 1991)

Prove a (3+eps)n rank lower bound for an explicit n x n x n tensor — the record is 3n − Theta(log n) while random tensors have rank ~n^2/3

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10tensorsalgebraicarithmetic-circuitsasymptotic-rankmatrix-multiplication

⟳ on the unconditional loop: any improved explicit rank bound is itself unconditional and transfers to bilinear circuit complexity (Strassen, J. Reine Angew. Math. 1973); explicit order-d tensors of rank n^{d(1-o(1))} would give superpolynomial arithmetic formula lower bounds (Raz, STOC 2010 / JACM 2013)

Beat Ω(n²): the best proof-size lower bound for Frege — and even Extended Frege — has been quadratic for three decades

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10proof-complexityfregeextended-fregemagnificationnp-vs-conp

⟳ Cook–Reckhow (J. Symbolic Logic 44(1), 1979): superpolynomial bounds for every proof system ⟺ NP ≠ coNP, with Frege/EF the canonical next systems; Müller & Pich (Annals of Pure and Applied Logic 2020, ECCC TR17-144, Prop. 4.14): if truth-table formulas encoding a circuit lower bound are hard for constant-depth Frege, the succinct lb-formulas are hard for unrestricted Frege; Pich (ECCC TR23-199): superpolynomial lower bounds for EF plus witnessing axioms would yield superpolynomial circuit lower bounds for SAT, if the witnessing formulas are tautologies

Beat Baur–Strassen: prove an ω(n log n) lower bound for general arithmetic circuits — the record has stood since 1983 while ABPs and formulas fell to n²

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10arithmetic-circuitsalgebraiclower-boundsvp-vs-vnp

⟳ the Kabanets–Impagliazzo loop: superpolynomial arithmetic circuit lower bounds for an explicit family (e.g. the Permanent) derandomize blackbox PIT, and conversely PIT ∈ P implies NEXP ⊄ P/poly or the Permanent has no poly-size arithmetic circuits (Kabanets & Impagliazzo, comput. complexity 13, 2004); any ω(n log n) bound is itself unconditional progress toward VP ≠ VNP

Beat half-exponential circuit lower bounds for MAEXP: stuck since 1999 while Σ2E hit near-maximum 2^n/n and AMEXP got there with sub-exponential advice — the advice-free Merlin–Arthur classes are the last holdouts

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexitymerlin-arthurhalf-exponentialkarp-liptonlower-bounds

⟳ the payoff is the unconditional lower bound itself: a 2^{n^ε}-size bound for MAEXP would be the first super-half-exponential lower bound for a Merlin–Arthur class, and the published route is concrete — the iterative win-win paradigm plus the Shaltiel–Umans / van Melkebeek–Sdroievski uniform hardness-vs-randomness connection already yields 2^n/n for AMEXP with 2^{n^ε} advice (Chen–Li–Liang, STOC 2025); removing the advice closes the loop

Majority vs AC0[⊕]: close the gap between 2^{Ω(n^{1/(2d−4)})} and exp(Õ(n^{(2/3)·1/(d−4)})) — the Razborov–Smolensky exponent has moved once in thirty years

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexityac0ppolynomial-methodlower-boundsmajority

⟳ already unconditional — a better exponent at any depth d ≥ 5, or a better circuit for Majority, is a new record; one magnification step up, Gap-MKtP ∉ AC0[6][N^{1+ε}] implies EXP ⊄ AC0[6] (Oliveira, Pich & Santhanam, CCC 2019, ECCC TR18-158), and an n^{1+ε} lower bound against AC0_{d+2}[m] for any 2^{n^β}-sparse NP language implies NP ⊄ AC0_d[m][n^k] for all k (Chen, Jin & Williams, FOCS 2019, ECCC TR19-118)

Explicit matrix rigidity: beat Omega((N^2/r) log(N/r)) in Valiant's regime, or push the new superlogarithmic-rank rigidity of Walsh–Hadamard toward Razborov rigidity

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10rigiditylinear-circuitscommunication-complexityalgebraic

⟳ direct: Valiant-rigidity gives unconditional superlinear lower bounds for log-depth linear circuits (Valiant, MFCS 1977); Razborov-rigidity separates the communication analogue of PH (Razborov 1989; Wunderlich, Comput. Complexity 2012)

Cross the hardness-magnification threshold: Gap-MCSP has an unconditional N^{2−o(1)} formula lower bound, while N^{1+ε} against circuits — for the same problem — implies NP ⊄ P/poly

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexitymcsphardness-magnificationformulasmeta-complexity

⟳ an N^{2+ε} B2-formula (or N^{3+ε} U2-formula) lower bound for Gap-MKtP[2^{βn}, 2^{βn}+cn] implies EXP ⊄ NC1 (Oliveira–Pich–Santhanam, CCC 2019); an N^{1+ε} lower bound for MCSP[2^{√n}] against one-tape Turing machines or poly(s)-space streaming algorithms implies P ≠ NP (McKay, Murray & Williams, STOC 2019)

Noncommutative circuits after the 2026 quadratic: the palindrome bound Ω(n²) is tight — an n^{1.19} bound at constant degree would amplify to exponential

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10arithmetic-circuitsnoncommutativehardness-amplificationlower-bounds

⟳ the CILM amplifier is the loop: Ω(n^{ω/2+ε}) for an explicit constant-degree noncommutative polynomial yields explicit families requiring exp(m^c)-size noncommutative circuits (Theorem 1.2, CCC 2018), and poly-degree bounds beyond n^{ω/2+ε} lift to arbitrary polynomial bounds (Theorem 1.1); a noncommutative determinant in poly size would even give VP = VNP (Arvind–Srinivasan, cited there)

Widen the only unconditional NTIME vs DTIME separation: the record is NTIME[n√(log* n)] ≠ DTIME[n√(log* n)] on multitape TMs — n log n is open, and RAMs are open even at linear time

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10structural-complexityhierarchiesnondeterminismturing-machinesunconditional

⟳ any extension is itself a new unconditional separation; Santhanam 2001 gives the hierarchy loop: either P ≠ L, or NTIME(t) ≠ DTIME(t) for every polynomially bounded constructible t — so pushing the separation up the time scale collides directly with P vs L, and a RAM version would be the first nondeterminism-vs-determinism separation in the model where fine-grained complexity actually lives

Push the determinantal complexity of the n x n permanent past Mignon–Ressayre's n²/2 — quadratic since 2004, upper bound 2^n − 1, and superpolynomial is exactly Valiant's conjecture

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10arithmetic-circuitspermanentdeterminantvp-vs-vnpgct

⟳ Valiant's program, fully published: dc(Perm_n) = n^{O(1)} iff VNP = VBP, since the determinant is complete for VBP (= VP_ws) under p-projections and the permanent is VNP-complete in characteristic ≠ 2 (Valiant, STOC 1979; Toda 1992; Malod & Portier, J. Complexity 24, 2008) — so any superpolynomial dc bound unconditionally separates VNP from VBP

Base the m^2 hardness of sparse Radius on SETH — today it rests only on the Hitting Set conjecture

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10graphsradiushitting-setsethquantifiers

⟳ hardness side: deriving the Hitting Set conjecture from SETH by a deterministic reduction would refute NSETH, since Hitting Set is in (N ∩ coN)TIME[O(m)] (Carmosino et al., ITCS 2016, Lemma 5.6), and NSETH's failure implies E^NP lacks linear-size series-parallel circuits (ibid., Thm 4.1)

Prove a superpolynomial lower bound for dag-like resolution over parities — regular fell in 2024, depth N^{2−ε} in 2026, the general system still has none

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10proof-complexityres-parityliftingcommunication-complexitynp-vs-conp

⟳ Res(⊕) is a subsystem of AC0[2]-Frege (Itsykson & Sokolov, Annals of Pure and Applied Logic 171(1), 2020), the weakest natural system in Cook's program with no superpolynomial bound; Cook–Reckhow (J. Symbolic Logic 44(1), 1979): superpolynomial bounds for every propositional proof system ⟺ NP ≠ coNP

Push the SAT time-space lower bound past n^{2cos(pi/7)} ≈ n^{1.801} — the exponent is proved optimal for the entire known proof technique

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10lower-boundssattime-spacealternation-tradingautomated-proof-search

⟳ already unconditional — this is a lower bound against all algorithms in the model; any c ≥ 1.802 is a new unconditional theorem about SAT, and c = 2 would settle a 25-year program

Link the Set Cover Conjecture to SETH — or solve Set Cover in O((2-ε)^n)

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10set-coversethscchypothesesexponential-timereductions

⟳ the hardness side is loop-shaped: a proof of SCC would refute Strassen's asymptotic rank conjecture (Björklund & Kaski, STOC 2024, arXiv:2310.11926) and yield explicit tensor families of asymptotic rank ≥ N^{1.08} (Pratt, STOC 2024, arXiv:2311.02774) — an unconditional algebraic lower bound; no analogous published path from the algorithmic side

Cross the Filmus–Pitassi–Santhanam threshold: depth-d Frege records for Tseitin and PHP are 2^{Ω̃(n^{1/d})}, while any 2^{n^{ω(1/d)}} bound for CNFs implies superpolynomial Frege lower bounds

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10proof-complexitybounded-depth-fregeswitching-lemmatseitinphpmagnification

⟳ Filmus–Pitassi–Santhanam: a 2^{n^{ω(1/d)}} size lower bound for refuting CNFs in depth-d Frege translates into a superpolynomial lower bound for unrestricted Frege; combined with Cook–Reckhow (J. Symbolic Logic 44(1), 1979) this is the published magnification route from small-depth records to NP vs coNP

Prove n^{1+ε} hardness for any sparse NP language — Tal's n^{2−ε} formulas-of-parities bound already clears the magnification threshold, but for a non-sparse function

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexityhardness-magnificationsparse-languagesformulasmeta-complexity

⟳ for any family of 2^{n^β}-sparse NP languages: outside Circuit[n^{1+ε}] implies NP ⊄ Circuit[n^k] for all k; outside U2-Formula-⊕[n^{1+ε}] or B2-Formula[n^{2+ε}] or U2-Formula[n^{3+ε}] implies NP ⊄ Formula[n^k]; outside BP[n^{2+ε}] implies NP ⊄ BP[n^k]; with AC0[m] and TC0 analogues, and it even suffices to fool n^{1+ε}-time n^ε-space deterministic algorithms with n^ε advice (Chen, Jin & Williams, FOCS 2019, ECCC TR19-118, Theorems 1.1–1.2)

TC0 wires: parity needs n^{1+c^{−d}} wires with c ≈ 2.41 — prove the same shape for every c > 1 for an NC1-complete function and TC0 ≠ NC1 falls out

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10circuit-complexitytc0wireshardness-magnificationthreshold-circuits

⟳ if for every c > 1 and all sufficiently large d, some NC1-complete function requires n^{1+c^{−d}} wires in depth-d TC0, then TC0 ≠ NC1 (Chen & Tell, STOC 2019, ECCC TR18-199 — the known c ≈ 2.41 is the only thing in the way); a single fixed-ε bound of n^{1+ε} wires at every constant depth for Boolean Formula Evaluation already gives TC0 ≠ NC1 (Allender & Koucký, JACM 2010); and Gap-MKtP ∉ TC0[N^{1+ε}] implies EXP ⊄ TC0 (Oliveira, Pich & Santhanam, CCC 2019, ECCC TR18-158)

Make the Thorup–Zwick distance-oracle bound unconditional: stretch 2k−1 in o(n^{1+1/k}) space, or a matching lower bound not resting on the Erdős girth conjecture

open⟳ loop-capableFind the missing hardnessconfidence: highverified 2026-08-10graphsdistance-oraclesspannersgirth-conjecturedata-structures

⟳ resolution (b) is itself unconditional: exhibiting girth-(2k+2) graphs with n^{1+1/k} edges (the Erdős girth conjecture, open beyond k = 1, 2, 3, 5) turns Thorup–Zwick's incompressibility argument (JACM 2005) into an unconditional Ω(n^{1+1/k})-bit space bound — a combinatorial gate, not a complexity-hypothesis one; no route to uniform separations known

Pin down catalytic logspace against P: prove CL ⊆ P (now equivalent to making every CL machine run in polynomial time) or P ⊆ CL

open⟳ loop-capableComplete an equivalenceconfidence: highverified 2026-08-10space-complexitycatalyticderandomizationstructural

⟳ on the catalytic loop: a proof that CL ⊄ P would unconditionally separate P from ZPP (since CL ⊆ ZPP, Buhrman et al., STOC 2014); catalytic machinery also powers Cook–Mertz Tree Evaluation and Williams' TIME[t] ⊆ SPACE[sqrt(t log t)] (STOC 2025), whose collision with the space hierarchy theorem already gives unconditional SPACE[s] ⊄ TIME[s^{2-eps}]

Find a fine-grained reduction between any two of the three pillars — SETH/OV, 3SUM, APSP — in any direction

open⟳ loop-capableComplete an equivalenceconfidence: highverified 2026-08-10pillarsseth3sumapspreductionsstructural

⟳ a deterministic fine-grained reduction from CNF-SAT to 3SUM or APSP would refute NSETH (both targets have fast co-nondeterministic algorithms), and NSETH's failure implies E^NP lacks linear-size series-parallel circuits (Carmosino–Gao–Impagliazzo–Mihajlin–Paturi–Schneider, ITCS 2016, Thm 4.1, via Jahanjou–Miles–Viola, ICALP 2015)

Close the (log log n)^2 gap in amortized dynamic connectivity: O(log n (log log n)^2) vs Ω(log n)

open⟳ loop-capableTighten an overheadconfidence: highverified 2026-08-10dynamicconnectivitycell-probedata-structurespolylog

⟳ lower-bound side is on the unconditional loop: cell-probe bounds need no conjectures, so any ω(log n) bound for connectivity is itself a new unconditional result — and the first separation from partial sums (cf. Pătraşcu & Demaine, SICOMP 2006); no published unconditional consequence from improving the algorithm

Superfast derandomization: beat the n · T overhead for worst-case BPTIME[T], or weaken the assumptions for free-lunch T^{1+eps}

open⟳ loop-capableTighten an overheadconfidence: highverified 2026-08-10derandomizationhardness-vs-randomnesstargeted-prgnsethone-way-functions

⟳ near-equivalence theorems make any unconditional version pay out directly: superfast derandomization implies lower bounds for multi-bit functions against uniform probabilistic algorithms on almost all inputs, and conversely (Chen & Tell, FOCS 2021) — so proving the record's conclusion unconditionally yields unconditional uniform lower bounds

Improve TIME[t] ⊆ SPACE[sqrt(t log t)]: shave the sqrt(log t) factor, or push the exponent below 1/2

open⟳ loop-capableTighten an overheadconfidence: highverified 2026-08-10space-complexitysimulationstree-evaluationstructural

⟳ already on the loop: via the space hierarchy theorem the simulation yields unconditional separations — for every eps > 0 there are problems in SPACE[n] not solvable in TIME[n^{2-eps}] (Williams, STOC 2025) — and any improvement to the simulation mechanically strengthens this unconditional time lower bound (exponent 1/2 - c would push it past quadratic)

Cutting Planes beyond interpolation: the record is 2^{Ω̃(n)} for random Θ(log n)-CNFs — random constant-width CNFs and Tseitin have no superpolynomial bound at all

open⟳ loop-capableTransfer hardnessconfidence: highverified 2026-08-10proof-complexitycutting-planesrandom-cnfinterpolationmonotone-circuits

⟳ Cook–Reckhow (J. Symbolic Logic 44(1), 1979): superpolynomial bounds for successively stronger systems is the program toward NP ≠ coNP, and CP is among the strongest systems with unconditional bounds; via Pudlák's feasible interpolation (J. Symbolic Logic 62(3), 1997), CP size bounds are equivalent to monotone-real-circuit lower bounds, so every extension of the CP record is simultaneously an unconditional circuit lower bound

Transfer Rubinstein's SETH-hardness of (1+eps)-approximate closest pair from the bichromatic case to the monochromatic case, or find a subquadratic algorithm

open⟳ loop-capableTransfer hardnessconfidence: highverified 2026-08-10nearest-neighborgeometryfine-grainedsethdistributed-pcp

⟳ refutation side: a subquadratic exact (or n^{1.5-delta} approximate) algorithm refutes SETH via the Karthik–Manurangsi reduction, and SETH's failure implies E^NP lacks linear-size series-parallel circuits (Jahanjou–Miles–Viola, ICALP 2015; stated as Cor. B.3 in Carmosino et al., ITCS 2016)

The wider web (53)

No published path to an unconditional result — yet. These tighten the web of reductions, and finding an endgame for one of them is itself a contribution.

Open problems in complexity theory

The loop-capable spine (51)

The wider web (53)

Improve an algorithm (37)

Find the missing hardness (11)

Complete an equivalence (2)

Tighten an overhead (3)