[{"language":[{"iso":"eng"}],"user_id":"71541","_id":"57866","external_id":{"arxiv":["2412.19623"]},"status":"public","abstract":[{"lang":"eng","text":"The theory of Total Function NP (TFNP) and its subclasses says that, even if\r\none is promised an efficiently verifiable proof exists for a problem, finding\r\nthis proof can be intractable. Despite the success of the theory at showing\r\nintractability of problems such as computing Brouwer fixed points and Nash\r\nequilibria, subclasses of TFNP remain arguably few and far between. In this\r\nwork, we define two new subclasses of TFNP borne of the study of complex\r\npolynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental\r\nTheorem of Algebra (SFTA). The first of these is based on B\\'ezout's theorem\r\nfrom algebraic geometry, marking the first TFNP subclass based on an algebraic\r\ngeometric principle. At the heart of our study is the computational problem\r\nknown as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR),\r\nfirst studied by [Laumann, L\\\"auchli, Moessner, Scardicchio, and Sondhi 2010].\r\nAmong other results, we show that QSAT with SDR is MHS-complete, thus giving\r\nnot only the first link between quantum complexity theory and TFNP, but also\r\nthe first TFNP problem whose classical variant (SAT with SDR) is easy but whose\r\nquantum variant is hard. We also show how to embed the roots of a sparse,\r\nhigh-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is\r\ncontained in a zero-error version of MHS. We conjecture this construction also\r\nworks in the low-error setting, which would imply SFTA is contained in MHS."}],"type":"conference","publication":"17th Innovations in Theoretical Computer Science Conference (ITCS 2026)","title":"An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem","date_created":"2024-12-30T13:55:27Z","author":[{"last_name":"Aldi","full_name":"Aldi, Marco","first_name":"Marco"},{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"},{"last_name":"Rudolph","id":"57863","full_name":"Rudolph, Dorian","first_name":"Dorian"}],"volume":362,"date_updated":"2026-01-23T07:53:03Z","citation":{"short":"M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), 2026, p. 7:1-7:24.","bibtex":"@inproceedings{Aldi_Gharibian_Rudolph_2026, title={An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem}, volume={362}, booktitle={17th Innovations in Theoretical Computer Science Conference (ITCS 2026)}, author={Aldi, Marco and Gharibian, Sevag and Rudolph, Dorian}, year={2026}, pages={7:1-7:24} }","mla":"Aldi, Marco, et al. “An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum  Satisfiability Problem.” <i>17th Innovations in Theoretical Computer Science Conference (ITCS 2026)</i>, vol. 362, 2026, p. 7:1-7:24.","apa":"Aldi, M., Gharibian, S., &#38; Rudolph, D. (2026). An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem. <i>17th Innovations in Theoretical Computer Science Conference (ITCS 2026)</i>, <i>362</i>, 7:1-7:24.","ama":"Aldi M, Gharibian S, Rudolph D. An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem. In: <i>17th Innovations in Theoretical Computer Science Conference (ITCS 2026)</i>. Vol 362. ; 2026:7:1-7:24.","ieee":"M. Aldi, S. Gharibian, and D. Rudolph, “An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem,” in <i>17th Innovations in Theoretical Computer Science Conference (ITCS 2026)</i>, 2026, vol. 362, p. 7:1-7:24.","chicago":"Aldi, Marco, Sevag Gharibian, and Dorian Rudolph. “An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum  Satisfiability Problem.” In <i>17th Innovations in Theoretical Computer Science Conference (ITCS 2026)</i>, 362:7:1-7:24, 2026."},"intvolume":"       362","page":"7:1-7:24","year":"2026","publication_status":"published"},{"status":"public","abstract":[{"lang":"eng","text":"The Quantum k-SAT problem is the quantum generalization of the k-SAT problem.\r\nIt is the problem whether a given local Hamiltonian is frustration-free.\r\nFrustration-free means that the ground state of the k-local Hamiltonian\r\nminimizes the energy of every local interaction term simultaneously. This is a\r\ncentral question in quantum physics and a canonical QMA_1-complete problem. The\r\nQuantum k-SAT problem is not as well studied as the classical k-SAT problem in\r\nterms of special tractable cases, approximation algorithms and parameterized\r\ncomplexity. In this paper, we will give a graph-theoretic study of the Quantum\r\nk-SAT problem with the structures core and radius. These hypergraph structures\r\nare important to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT\r\ninstance in polynomial time if the derived hypergraph has a core of size n-m+a,\r\nwhere a is a constant, and the radius is at most logarithmic. If it exists, we\r\ncan find a core of size n-m+a with the best possible radius in polynomial time,\r\nwhereas finding a general minimum core with minimal radius is NP-hard."}],"publication":"arXiv:2506.17066","type":"preprint","language":[{"iso":"eng"}],"user_id":"71541","external_id":{"arxiv":["2506.17066"]},"_id":"60432","citation":{"ama":"Kremer S-L, Rudolph D, Gharibian S. Quantum k-SAT Related Hypergraph Problems. <i>arXiv:250617066</i>. Published online 2025.","ieee":"S.-L. Kremer, D. Rudolph, and S. Gharibian, “Quantum k-SAT Related Hypergraph Problems,” <i>arXiv:2506.17066</i>. 2025.","chicago":"Kremer, Simon-Luca, Dorian Rudolph, and Sevag Gharibian. “Quantum K-SAT Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>, 2025.","mla":"Kremer, Simon-Luca, et al. “Quantum K-SAT Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>, 2025.","bibtex":"@article{Kremer_Rudolph_Gharibian_2025, title={Quantum k-SAT Related Hypergraph Problems}, journal={arXiv:2506.17066}, author={Kremer, Simon-Luca and Rudolph, Dorian and Gharibian, Sevag}, year={2025} }","short":"S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).","apa":"Kremer, S.-L., Rudolph, D., &#38; Gharibian, S. (2025). Quantum k-SAT Related Hypergraph Problems. In <i>arXiv:2506.17066</i>."},"year":"2025","title":"Quantum k-SAT Related Hypergraph Problems","date_created":"2025-06-27T06:56:35Z","author":[{"first_name":"Simon-Luca","full_name":"Kremer, Simon-Luca","last_name":"Kremer"},{"first_name":"Dorian","last_name":"Rudolph","id":"57863","full_name":"Rudolph, Dorian"},{"first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag","id":"71541"}],"date_updated":"2025-06-27T06:57:03Z"}]