Copertina

Optimal Proof Systems for Complex Sets are Hard to Find

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Egidy, Fabian, Glaßer, Christian
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Recursive Jump Operators and Optimal Proof Systems
di: Egidy, Fabian
Pubblicazione: (2026)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
di: Egidy, Fabian
Pubblicazione: (2026)

An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
di: Dingel, David, et al.
Pubblicazione: (2024)

Hard CNF Instances for Ideal Proof Systems
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2026)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
di: Atserias, Albert, et al.
Pubblicazione: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
di: Casteigts, Arnaud, et al.
Pubblicazione: (2026)

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
di: Ren, Hanlin, et al.
Pubblicazione: (2025)

Hardness of SetCover Reoptimization
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
di: Ramya, C., et al.
Pubblicazione: (2025)

Separations in Proof Complexity and TFNP
di: Göös, Mika, et al.
Pubblicazione: (2022)

A Parameterized-Complexity Framework for Finding Local Optima
di: Ganian, Robert, et al.
Pubblicazione: (2026)

From Proof Complexity to Circuit Complexity via Interactive Protocols
di: Arteche, Noel, et al.
Pubblicazione: (2024)

Near Optimal Hardness of Approximating $k$-CSP
di: Minzer, Dor, et al.
Pubblicazione: (2025)

The Complexity of Order-Finding for ROABPs
di: Bhargava, Vishwas, et al.
Pubblicazione: (2024)

Proof Complexity and Feasible Interpolation
di: Tabatabai, Amirhossein Akbar
Pubblicazione: (2025)

Multiparty Communication Complexity of Collision Finding
di: Beame, Paul, et al.
Pubblicazione: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
di: Lee, Euiwoong, et al.
Pubblicazione: (2024)

Hardness of Finding Kings and Strong Kings
di: Alaoui, Ziad Ismaili, et al.
Pubblicazione: (2025)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
di: Li, Jiawei, et al.
Pubblicazione: (2024)

Symmetric Proofs in the Ideal Proof System
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

Proof Systems Based on Structured Circuits
di: Micun, Matthäus, et al.
Pubblicazione: (2026)

The Complexity of Finding Missing Answer Repairs
di: Comer, Jesse, et al.
Pubblicazione: (2026)

Proof Complexity of Linear Logics
di: Tabatabai, Amirhossein Akbar, et al.
Pubblicazione: (2026)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
di: Chukhin, Nikolai, et al.
Pubblicazione: (2024)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2024)

Optimal Union Probability Interval Is NP-Hard
di: Kaski, Petteri, et al.
Pubblicazione: (2026)

Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation
di: Çivril, Ali
Pubblicazione: (2023)

Optimal Communication Complexity of Chained Index
di: Sundaresan, Janani
Pubblicazione: (2024)

On the Complexity of Target Set Selection in Simple Geometric Networks
di: Dvořák, Michal, et al.
Pubblicazione: (2023)

Optimally Blending Honeypots into Production Networks: Hardness and Algorithms
di: Zaman, Md Mahabub Uz, et al.
Pubblicazione: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
di: Elbaz, Tal, et al.
Pubblicazione: (2025)

Fine-Grained Complexity via Quantum Natural Proofs
di: Chen, Yanlin, et al.
Pubblicazione: (2025)

On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets
di: Asadi, Ali, et al.
Pubblicazione: (2026)

The Complexity of Finding and Counting Subtournaments
di: Döring, Simon, et al.
Pubblicazione: (2025)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
di: Chavrimootoo, Michael C., et al.
Pubblicazione: (2026)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
di: Bilò, Davide, et al.
Pubblicazione: (2024)

Barriers to Complexity-Theoretic Proofs that "AGI" Using Machine Learning is Impossible
di: Guerzhoy, Michael
Pubblicazione: (2024)

The Parameterized Complexity of Terminal Monitoring Set
di: Aravind, N. R., et al.
Pubblicazione: (2024)