{"id":"f991e250-801e-4011-8f3f-c110b48013c1","arxiv_id":"2412.19623","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New TFNP subclasses MHS (from Bézout's theorem) and SFTA (from the Fundamental Theorem of Algebra) are defined, and QSAT with SDR is proven MHS-complete.","lead":"This paper defines two new complexity classes for total search problems, MHS and SFTA, based on the mathematics of polynomial equations. It shows that the quantum satisfiability problem with a System of Distinct Representatives is complete for one of these classes, giving the first formal link between quantum complexity and TFNP.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Precision transfer in Theorem 59 conflates squared and absolute residuals: PRODSAT energy ε yields MHS residual √(mε), not Θ(ε), so the formal containment as stated fails.","rationale":"The reader correctly identified the precision-transfer step in Theorem 59 as the weakest assumption, and I agree that this step is load-bearing. My analysis sharpens the concern: it is not merely that explicit Lipschitz constants are missing; the definitions themselves create a square-root mismatch. A rank-1 projector gives energy |f_i(Y)|², while the MHS residual in Definition 57 is Σ|f_i(Y)|. Therefore a PRODSAT solution of energy ε only guarantees MHS residual √(mε), which is not Θ(ε) for small ε. This makes the formal containment statement in Theorem 59(1) incorrect as written. The qualitative claim that QSAT with SDR is complete for a TFNP class based on algebraic geometry may survive a repair, since the hardness direction is unaffected and one could redefine MHS with squared residual or adjust precision parameters. But the paper's central completeness statement depends on this transfer, so the formal claim needs correction. I do not see other objections of comparable weight: the algebraic-geometric existence proofs are elegant, the WSDR framework is coherent, and the conjectural parts are clearly labelled. The paper is significant and worth publishing after the precision issue is resolved, hence CONDITIONAL rather than REJECT.","tokens_in":49972,"tokens_out":7338,"duration_ms":74004,"concrete_test":"Re-derive the transfer for a single 1-local clause: let F={f} with f(x)=⟨0|x⟩=x_0 on one qubit variable group X=(x_0,x_1), normalized. Encode as Π=|0⟩⟨0|. Take the product state |ψ⟩=(√ε,√(1−ε))^T. Then PRODSAT energy ⟨ψ|Π|ψ⟩=ε, but MHS residual |f(Y)|=|√ε|=√ε. Verify whether any constant C>0 satisfies √ε ≤ Cε for all inverse-exponential ε; it does not. This settles that Theorem 59(1) as stated cannot hold for the given definitions. If the intended MHS residual is instead squared, the fix should be stated explicitly and the completeness statement re-checked.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing point is the precision-transfer step in Theorem 59(1), but the problem is sharper than missing Lipschitz constants. Under Definitions 14 and 57, a rank-1 clause Π_i=|ϕ_i⟩⟨ϕ_i| corresponds to the polynomial f_i(Y)=⟨ϕ_i|Y⟩, and the PRODSAT witness condition is Σ_i ⟨ψ|Π_i|ψ⟩ = Σ_i |f_i(Y)|² ≤ ε. The MHS residual is Σ_i |f_i(Y)|. For a single clause (m=1), an assignment with |f_1|=√ε has energy ε but MHS residual √ε. No Lipschitz bound can turn this into O(ε) for inverse-exponential ε. Thus the sentence in the proof of Theorem 59, '...follows by the Lipschitz continuity of polynomials on a compact set...', is not merely under-derived; as written it is inconsistent with the two definitions. The hardness direction MHS(ε) → PRODSAT(Θ(ε)) is not affected, since Σ|f_i|≤ε implies Σ|f_i|²≤ε². But containment PRODSAT(ε) ∈ MHS(ε) fails as stated. The theorem could be repaired by redefining the MHS residual as Σ|f_i|², or by restating containment as MHS(√(mε)); either way, Theorem 3's Θ(ε)-completeness claim needs re-examination.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":50246,"tokens_out":13180,"duration_ms":122133,"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":[{"comment":"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.","section":"Definition 57, Theorem 59"}],"minor_comments":[{"comment":"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":"Section 5.2, proof of Theorem 59(1)"},{"comment":"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.","section":"Section 6.3.3, proof of Theorem 7"},{"comment":"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.","section":"Lemma 68"},{"comment":"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.","section":"Theorem 3 and Theorem 59"}],"recommendation":"major_revision","confidential_remarks":"The precision mismatch in the completeness theorem is a genuine formal issue, but it is localized and repairable. The surrounding contributions are substantial and the exposition is generally careful. I do not see a circularity or selective-citation problem; the paper's stated limitations are handled honestly. A revised version that fixes the residual metric in Definition 57 and reworks the precision statements in Theorem 59 and Theorem 3 would be well within the scope of a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead 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.\n\nWhat 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.\n\nWhere 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.\n\nMinor 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.\n\nWho 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.\n\nRecommendation: send to peer review. After the precision fix, I would cite it.","headline":"A genuinely new TFNP subclass and a real quantum link, but the Θ(ε)-completeness claim has a precision-transfer bug that needs repair.","tokens_in":50807,"tokens_out":1826,"would_cite":true,"duration_ms":18805,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q12","13P15","14Q20"],"pacs":["03.67.-a","02.10.Xm"],"model":"deepseek-v4-flash","headline":"Quantum SAT with distinct representatives is hard for a new TFNP class built on Bézout's theorem.","keywords":["TFNP","Quantum SAT","Multi-homogeneous systems","Bézout's theorem","Product state solutions","System of distinct representatives","Sparse polynomials","Completeness"],"falsifier":"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.","tokens_in":49766,"feed_emoji":"🧮","tokens_out":3193,"duration_ms":24576,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quantum SAT with SDR is hard for a new TFNP class from algebraic geometry","feed_subtitle":"Finding product-state solutions to QSAT with distinct representatives is MHS-complete, linking quantum complexity and TFNP.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Showed that QSAT with SDR on qubits always has a solution, which is the classical analogue and the base case for the qudit generalization.","marker":"[LLM+10]"},{"why":"Provides the multi-homogeneous Bézout theorem that is the existence principle underlying the MHS class.","marker":"[Sha74]"},{"why":"Defines TFNP and the standard subclasses, and provides the reduction framework used to define MHS and SFTA.","marker":"[Pap94]"},{"why":"Showed that QSAT with SDR and an additional restriction is NP-hard, which is a key comparison and contrast for the MHS-completeness result.","marker":"[Goe19]"},{"why":"Provides Canny's Lemma, which is used to explore the relationship between MHS and SFTA, and to show that generic instances of QSAT with WSDR can be reduced to roots of a single polynomial.","marker":"[Can88]"},{"why":"Provides the parameterized algorithm for special cases of QSAT with SDR, which is extended in this paper to more general settings.","marker":"[AdBGS21]"},{"why":"Used to argue that roots of non-sparse polynomials can be approximated in poly(d) time, motivating the sparsity requirement in SFTA.","marker":"[Sch85]"}],"fun_headline_variants":["QSAT with SDR is MHS-complete: new TFNP class from algebraic geometry","Quantum SAT with distinct reps is hard and MHS-complete","First TFNP subclass from algebraic geometry: QSAT with SDR is hard","Classical SAT easy, quantum SAT hard: link to TFNP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["QSAT with SDR is MHS-complete: new TFNP class from algebraic geometry","Quantum SAT with distinct reps is hard and MHS-complete","First TFNP subclass from algebraic geometry: QSAT with SDR is hard","Classical SAT easy, quantum SAT hard: link to TFNP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000529,"raw_usage":{"total_tokens":2569,"prompt_tokens":983,"completion_tokens":1586,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":1505}},"tokens_in":599,"tokens_out":1586,"duration_ms":12212,"temperature":1.0,"reasoning_tokens":1505,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:10:25.115071+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}