An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

Dorian Rudolph; Marco Aldi; Sevag Gharibian

REVIEW 1 major objections 4 minor 12 references

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

T0 review · 1 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Quantum SAT with distinct representatives is hard for a new TFNP class built on Bézout's theorem.

desk verdict A genuinely new TFNP subclass and a real quantum link, but the Θ(ε)-completeness claim has a precision-transfer bug that needs repair. read the letter →

arxiv 2412.19623 v2 pith:C6FKYFHM submitted 2024-12-27 quant-ph cs.CC

Marco Aldi , Sevag Gharibian , Dorian Rudolph This is my paper · ORCID

classification quant-phcs.CC MSC 68Q1568Q1213P1514Q20 PACS 03.67.-a02.10.Xm

keywords TFNPQuantumSATMulti-homogeneoussystemsBézout'stheoremProductstatesolutionsSystemofdistinctrepresentativesSparsepolynomialsCompleteness

topics P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces two new subclasses of TFNP, the complexity class of search problems whose solutions are guaranteed to exist but may be hard to find. The first, Multi-homogeneous Systems (MHS), is based on Bézout's theorem from algebraic geometry, making it the first TFNP subclass rooted in that field. The second, Sparse Fundamental Theorem of Algebra (SFTA), is based on the fact that every complex polynomial has a root. The central claim is that Quantum SAT with a System of Distinct Representatives, a quantum analogue of a classically easy satisfiability problem, is complete for MHS, providing the first formal link between quantum complexity theory and TFNP. This is surprising because the classical version of the problem is easily solvable, while the quantum version is shown to be hard for a total search complexity class.

What carries the argument

The central machinery is the Multi-homogeneous Systems (MHS) complexity class, defined via systems of multi-homogeneous polynomial equations over complex numbers with a positive Bézout number. The proof of completeness relies on a weighted generalization of Systems of Distinct Representatives (WSDR), which encodes the existence of product state solutions to QSAT. A key technique is a mapping from qudits to qubits that preserves product state solutions and allows enforcing equality constraints via rank-1 projectors on the antisymmetric subspace. Additionally, the paper uses transfer functions, which are polynomial maps describing how a partial assignment to a quantum constraint forces an assignment to the remaining qubit, to embed roots of sparse polynomials into QSAT instances with SDR.

What would settle it

One could attempt to find a polynomial-time algorithm for QSAT with SDR on qubits, which would contradict the MHS-completeness result unless MHS collapses to P. Alternatively, one could try to find a reduction from MHS to a problem in a known easy class, or show that MHS is contained in a known TFNP class like PPAD, which would contradict the paper's conjecture that MHS is distinct. Another concrete falsifier is to find a counterexample to the conjecture SFTA ⊆ MHS by showing that a sparse polynomial can be solved in a way that cannot be embedded into QSAT with SDR while preserving the approximation factor.

Watch

Extended reading notes

Core claim

The paper's central discovery is that computing an epsilon-approximate product-state solution to k-QSAT on qudits with weighted SDR is MHS(Theta(epsilon))-complete, for inverse-exponential epsilon and constant degree and locality. In particular, QSAT with SDR on qubits is complete for the new TFNP subclass MHS, making it the first TFNP problem whose classical analogue is easy but whose quantum analogue is complete for a TFNP class. This establishes a formal connection between quantum complexity theory and TFNP, and implies that finding product-state solutions for these quantum systems is likely intractable, even though such solutions are guaranteed to exist.

Load-bearing premise

The proof's precision-transfer step in the hardness direction of Theorem 59 relies on the assumption that an epsilon-approximate solution of the PRODSAT instance yields a Theta(epsilon)-approximate solution of the MHS instance via Lipschitz continuity, but this is only stated informally and lacks explicit error analysis, particularly given inverse-exponential precision.

Editorial extensions

If this is right

QSAT with SDR is likely intractable, as it is complete for the new TFNP subclass MHS, despite always having a product-state solution.
The framework establishes the first formal link between quantum complexity theory and TFNP, opening a new direction for studying the complexity of quantum satisfiability problems.
MHS provides a new tool for proving intractability of problems, particularly those related to algebraic geometry and polynomial systems.
The containment of SFTA in a zero-error version of MHS suggests a close relationship between root-finding for sparse polynomials and the existence of product-state solutions to QSAT.
The efficient algorithms for special cases of QSAT with WSDR show that, despite the hardness result, there are still tractable subclasses of the problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If SFTA is contained in MHS, as conjectured, then finding roots of sparse high-degree polynomials would be as hard as finding product-state solutions to QSAT with SDR, potentially providing a link between computational algebra and quantum complexity.
The completeness result suggests that the search for product-state solutions in QSAT with SDR may require new algorithmic paradigms, and that quantum systems might be used as a computational resource to encode polynomial systems.
The connection between WSDRs and Bézout numbers could have further applications in algebraic geometry and computational complexity, as it provides a combinatorial interpretation of the Bézout number.
The idea of using algebraic geometry principles to define TFNP subclasses may extend to other existence theorems, such as those from intersection theory or the theory of resultants.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Read the Aldi-Gharibian-Rudolph paper. The central idea is good: define MHS via multi-homogeneous Bézout, prove QSAT with SDR/WSDR is complete for it, and introduce SFTA. That is a real first link between quantum complexity and TFNP, and the classical-vs-quantum contrast (SAT with SDR easy, QSAT with SDR hard) is worth stating.

What is genuinely new: MHS and SFTA as TFNP subclasses, the Chow ring proof of Theorem 1, the qudit-to-qubit reduction, the embedding of sparse polynomials into QSAT with SDR, and the parameterized algorithms. The paper is honest about what is open, especially SFTA ⊆ MHS.

Where it is soft: the containment direction of Theorem 59. The stress-test note is right, and it is not just a missing constant. Under the paper's own definitions, PRODSAT energy is Σ |f_i|², while the MHS residual is Σ |f_i|. For one clause, energy ε can give |f| = √ε, so the MHS residual is √ε, not Θ(ε). The one-sentence Lipschitz argument in the proof cannot fix that. The hardness direction is unaffected, and the theorem can be repaired by redefining the MHS residual as Σ|f_i|² or by restating containment as MHS(√(mε)). But as written, the Θ(ε)-completeness claim is too strong. This matters because the precision regime is inverse exponential, where the gap is large.

Minor points: Theorem 7's proof is a single sentence, but it is a direct reduction from Plaisted, so I would not worry much. Some parts of Section 7 are sketches, but they are clearly labeled as such.

Who this is for: complexity theorists working in TFNP and quantum Hamiltonian complexity. It deserves a serious referee; the referee should ask the authors to fix the precision statement and re-check the derived claims. The mathematical core is solid enough that I expect a clean repair.

Recommendation: send to peer review. After the precision fix, I would cite it.

Referee Report

1 major / 4 minor

Summary. This paper defines two new TFNP subclasses, MHS (multi-homogeneous systems, based on Bézout's theorem) and SFTA (sparse fundamental theorem of algebra). It introduces weighted systems of distinct representatives (WSDRs) and proves, via the Chow ring and via a qudit-to-qubit reduction, that QSAT with WSDR always has a product-state solution. The central complexity claim is Theorem 59: ε-approximate PRODSAT with WSDR is MHS-complete up to Θ(ε) precision. The paper also embeds roots of sparse univariate polynomials into QSAT with SDR, yielding SFTA containment in zero-error MHS, derives NP-hardness for slight variants of QSAT with SDR, and gives parameterized algorithms for special solvable cases.

Significance. If the main completeness statement is correctly formalized, this is a substantial contribution: it introduces the first TFNP subclass grounded in algebraic geometry, provides the first formal link between quantum satisfiability and TFNP, and highlights a clean contrast between classical SAT with SDR, which is easy, and its quantum analogue. The paper is unusually thorough in giving two independent proofs of the existence result, detailed reductions, and an honest discussion of the zero-error versus approximate gap for SFTA. The precision issue identified below is localized to the residual metric in Definition 57 and the proof of Theorem 59, and it appears repairable rather than fatal.

major comments (1)

[Definition 57, Theorem 59] The proof of Theorem 59 conflates squared and absolute residuals, and this undermines the Θ(ε)-completeness claim as stated. Under Definitions 14 and 57, a rank-1 clause Π_i = |φ_i⟩⟨φ_i| corresponds to a polynomial f_i(Y) = ⟨φ_i|ψ⟩, so the PRODSAT witness condition is Σ_i |f_i(Y)|² ≤ ε, whereas the MHS verification condition in Definition 57 is Σ_i |f_i(Y)| ≤ ε. For m = 1, an assignment with |f_1| = √ε has PRODSAT energy ε but MHS residual √ε. No Lipschitz bound on a compact set can convert √ε into Θ(ε) when ε is inverse exponential. Consequently, the containment direction 'PRODSAT(ε) ∈ MHS(ε)' is false as written. The standard solution-mapping direction of the hardness reduction in Theorem 59(2) also fails at this point: from a Θ(ε)-approximate PRODSAT solution one recovers only an MHS residual of order √(mε), not Θ(ε). The cleanest repair is to redefine the residual in Definition 57 as Σ_i |f_i|²; alternatively, the precision relations must be restated as Θ(√(mε)), or the hardness reduction must target Θ(ε²)-approximate PRODSAT. In any case, Theorem 3's 'MHS(Θ(ε))-complete' wording needs to be revised to match the corrected formal statement.

minor comments (4)

[Section 5.2, proof of Theorem 59(1)] The sentence 'without loss of generality, we may assume there are m qubits and n = m clauses, since if n < m an SDR cannot exist, and if n > m we can add trivially satisfied constraints' has the inequalities reversed: with m qubits and n clauses, an SDR requires n ≤ m, so n > m is the impossible case.
[Section 6.3.3, proof of Theorem 7] The sentence 'We can embed this problem into PRODSAT by adding a second adding a second polynomial in the above construction, which requires only a single unmatched edge' contains a duplicated phrase and does not spell out how the two polynomial encodings share the first qubit; since the result is already due to Goerdt, either present the shared-qubit construction explicitly or cite the result and omit the proof.
[Lemma 68] Please restate the root lower bound in the proof with explicit exponents; as typeset, the expression '(1 + c/d)c' and the subsequent inequality chain are hard to parse, even though the statement of the lemma appears correct.
[Theorem 3 and Theorem 59] The informal statement 'MHS(Θ(ε))-complete' should be reconciled with the formal Theorem 59 once the residual metric is fixed; it would help the reader to state explicitly whether the preservation is Θ(ε), Θ(√ε), or Θ(ε²) after the repair.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the precision-transfer issue in Theorem 59 is a correctness gap (ℓ1 vs ℓ2 residuals), not a construction that equates conclusion with input.

full rationale

This paper's principal derivations are self-contained against external mathematical facts: the existence results use Bézout's theorem and the Chow ring, the reductions in Theorems 43 and 59 are proved inside the paper, and the sparse-polynomial embedding in Theorem 70 is built from transfer-function gadgets proved as Lemma 73 rather than imported. The overlapping-author citations to AGS21/AdBGS21 are used for parameter-free hypergraph facts and algorithmic building blocks, not for the central equivalence claims; in particular, the MHS-hardness reduction's correctness is shown through the qudit-to-qubit map of Theorem 43 and the SDR matching argument in the proof of Theorem 59, neither of which assumes the target statement. The one genuinely fragile sentence, in the proof of Theorem 59, says that an epsilon-approximate PRODSAT solution gives a Theta(epsilon)-approximate MHS solution by Lipschitz continuity; this conflates the ℓ2 energy residual of PRODSAT with the ℓ1 polynomial residual of MHS and is a correctness concern, but it is not circular: no output is identified with an input by construction, and no fitted parameter is renamed as a prediction. The paper also explicitly acknowledges the unresolved approximate-embedding step for SFTA in Section 6.3, which is a stated limitation rather than a circular derivation. No step satisfies the criteria for self-definitional, fitted-input-called-prediction, self-citation-load-bearing, imported-uniqueness, or ansatz-smuggling circularity.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper's central claims rest on standard mathematical theorems, including Bezout, FTA, Hall, Landau, BKK, and Canny, all cited or proved in the appendix. There are no fitted parameters and no invented physical entities. The new constructs, such as the complexity classes MHS and SFTA and the WSDR framework, are defined and proven within the paper rather than postulated without evidence.

assumptions (8)

standard math Bezout's theorem for multi-homogeneous systems (Theorem 56)
Underpins the existence guarantee for MHS: a positive Bezout number implies a solution. Cited from Shafarevich and Morgan-Sommese; used in Definitions 52 and 57 and in the proof of Theorem 59.
standard math Chow ring intersection theory (Fact 36)
Used in the first proof of Theorem 1: if the product of hypersurface representatives is nonzero, the intersection is nonempty. This is standard algebraic geometry.
standard math Fundamental Theorem of Algebra (Theorem 64)
Guarantees existence of a root for SFTA; external to the paper.
standard math Landau's inequality (used in Lemma 68)
Bounds the Mahler measure to show a root exists within radius 1+ln(sqrt(s)d)/d; standard result, cited to Landau.
standard math Hall's Marriage Theorem for weighted hypergraphs (Theorem 23)
Provides the combinatorial criterion for WSDR existence; proved in Appendix A.
standard math BKK theorem (Berstein-Khovanskii-Kushnirenko, Theorem 81)
Used in Section 6.4 to count product solutions generically; external.
standard math Canny's Lemma (Lemma 79)
Gives the geometric resolution used in Theorem 83; external.
domain assumption Plaisted's NP-hardness results
Used for Theorems 6 and 7, specifically NP-hardness of deciding whether a sparse polynomial has a root of modulus 1 and whether two sparse polynomials have a common root. Accepted prior results.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem." pith.science (2026). https://pith.science/paper/C6FKYFHM

@misc{pith2026241219623,
  author       = {Pith},
  title        = {Pith review of: An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C6FKYFHM}},
  note         = {Machine review of arXiv:2412.19623}
}

read the original abstract

The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on B\'ezout's theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, L\"auchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA is contained in MHS.

Figures

Figures reproduced from arXiv: 2412.19623 by the authors.

**Figure 2.** (Left) The reduction of Theorem 59 before the reduction to qubits and without equality constraints, as illustrated on Example 54. The latter has equations f1 = x1y1y2 + x2y2y3, f2 = x1y1 + x2y2, and f3 = y1y2 + y2y3 with variable sets Z1 = {x1, x2} and Z2 = {y1, y2, y3}, n1 = 1, n2 = 2, m = 2, and d = 3. Variable sets Z1 and Z2 are represented by vertex sets {u} and {v, w}, respectively. (For simplicity, the reducti… view at source ↗

**Figure 3.** A PRODSAT instance with a star-like topology. The circles represent qutrits. All edges have size [PITH_FULL_IMAGE:figures/full_fig_p029_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Construction of Theorem 76 illustrated on input p(x) = x 3 − 4x + 5, i.e. d = 3. Then, q(x, y) = x 3 − 4xy2 + 5y 3 . Constraint ϕ1 is the equality constraint enforcing |v1⟩ ∝ |v0⟩. So, |v0⟩ = |v1⟩ = [x, y] T . Next, we wish to enforce |w2⟩ = [x 2 − 4y 2 , y2 ]. This is…

**Figure 5.** Figure 5: Pinwheel graph Γn for the case of n = 5. at v2,• to qubits and iterate the previous until we have a product assignments for all qutrits in terms of the initial assignment at v0 that satisfies all e and ϵ constraints. At this point we impose the ε• constraints and reali…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[5]

On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz

[BIQ+17] Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang. On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. In32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

work page 2017
[9]

Quantum 3-SAT Is QMA1-Complete

[GN13] David Gosset and Daniel Nagaj. Quantum 3-SAT Is QMA1-Complete. InProceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS ’13, pages 756–765, USA,

work page 2013
[262]

[BH16] Fernando G

ACM, New York, [2022]©2022. [BH16] Fernando G. S. L. Brandão and Aram W. Harrow. Product-State Approximations to Quantum States.Communications in Mathematical Physics, 342(1):47–80,

work page 2022
[1988]

Efficiently Computing Real Roots of Sparse Polyno- mials

[JS17] Gorav Jindal and Michael Sagraloff. Efficiently Computing Real Roots of Sparse Polyno- mials. In Proceedings of the 2017 ACM International Symposium on Symbolic and Alge- braic Computation, ISSAC ’17, pages 229–236, New York, NY, USA,

work page 2017
[2003]

Further Collapses in TFNP

[GHJ+22] Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. Further Collapses in TFNP. In37th Computational Com- plexity Conference (CCC 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

work page 2022
[2007]

Bounds on the quantum satisfiability threshold

[BMR09] S. Bravyi, C. Moore, and A. Russell. Bounds on the quantum satisfibility threshold. Available at arXiv.org quant-ph/0907.1297v2,

work page Pith review arXiv
[2009]

A Linear Time Algorithm for Quantum 2-SAT

[BG16] Niel de Beaudrap and Sevag Gharibian. A Linear Time Algorithm for Quantum 2-SAT. In Ran Raz, editor,31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:21, Dagstuhl, Germany,

work page 2016
[2010]

Intersection Classes in TFNP and Proof Complexity

[LPR24] Yuhao Li, William Pires, and Robert Robere. Intersection Classes in TFNP and Proof Complexity. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

work page 2024

Show all 12 references

[2012]

On the Com- plexity of Modulo-q Arguments and the Chevalley - Warning Theorem

[GKSZ20] Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis. On the Com- plexity of Modulo-q Arguments and the Chevalley - Warning Theorem. In35th Com- putational Complexity Conference (CCC 2020). Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

2020
[2016]

[BEKT22] Evangelos Bartzos, Ioannis Z

Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. [BEKT22] Evangelos Bartzos, Ioannis Z. Emiris, Ilias S. Kotsireas, and Charalambos Tzamos. Bounding the number of roots of multi-homogeneous systems. InISSAC ’22—Proceedings of the 2022 International Symposium on Symbolic and A...

2022
[2020]

Linear Time Algo- rithm for Quantum 2SAT

[ASSZ16] Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang. Linear Time Algo- rithm for Quantum 2SAT. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors,43rd International Colloquium on Automata, Lan- guages, and Programmin...

2016
[2024]

Computing Minimal Multi-homogeneous Bézout Numbers Is Hard

[MM05] Gregorio Malajovich and Klaus Meer. Computing Minimal Multi-homogeneous Bézout Numbers Is Hard. In Volker Diekert and Bruno Durand, editors, STACS 2005, pages 244–255, Berlin, Heidelberg,

2005

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [5]

On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz

[BIQ+17] Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang. On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. In32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

work page 2017

[2] [9]

Quantum 3-SAT Is QMA1-Complete

[GN13] David Gosset and Daniel Nagaj. Quantum 3-SAT Is QMA1-Complete. InProceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS ’13, pages 756–765, USA,

work page 2013

[3] [262]

[BH16] Fernando G

ACM, New York, [2022]©2022. [BH16] Fernando G. S. L. Brandão and Aram W. Harrow. Product-State Approximations to Quantum States.Communications in Mathematical Physics, 342(1):47–80,

work page 2022

[4] [1988]

Efficiently Computing Real Roots of Sparse Polyno- mials

[JS17] Gorav Jindal and Michael Sagraloff. Efficiently Computing Real Roots of Sparse Polyno- mials. In Proceedings of the 2017 ACM International Symposium on Symbolic and Alge- braic Computation, ISSAC ’17, pages 229–236, New York, NY, USA,

work page 2017

[5] [2003]

Further Collapses in TFNP

[GHJ+22] Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. Further Collapses in TFNP. In37th Computational Com- plexity Conference (CCC 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

work page 2022

[6] [2007]

Bounds on the quantum satisfiability threshold

[BMR09] S. Bravyi, C. Moore, and A. Russell. Bounds on the quantum satisfibility threshold. Available at arXiv.org quant-ph/0907.1297v2,

work page Pith review arXiv

[7] [2009]

A Linear Time Algorithm for Quantum 2-SAT

[BG16] Niel de Beaudrap and Sevag Gharibian. A Linear Time Algorithm for Quantum 2-SAT. In Ran Raz, editor,31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:21, Dagstuhl, Germany,

work page 2016

[8] [2010]

Intersection Classes in TFNP and Proof Complexity

[LPR24] Yuhao Li, William Pires, and Robert Robere. Intersection Classes in TFNP and Proof Complexity. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

work page 2024