Copertina

A Brief Note on a Recent Claim About NP-Hard Problems and BQP

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Chavrimootoo, Michael C.
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

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)

BQP, meet NP: Search-to-decision reductions and approximate counting
di: Gharibian, Sevag, et al.
Pubblicazione: (2024)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
di: Zschetzsche, Lilith, et al.
Pubblicazione: (2026)

The Acrobatics of BQP
di: Aaronson, Scott, et al.
Pubblicazione: (2021)

A Relativizing MIP for BQP
di: Aaronson, Scott, et al.
Pubblicazione: (2026)

NP-Hardness and a PTAS for the Pinwheel Problem
di: Kleinberg, Robert, et al.
Pubblicazione: (2026)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
di: Digulescu, Mircea-Adrian
Pubblicazione: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

NP-hard problems are not in BQP
di: Czerwinski, Reiner
Pubblicazione: (2023)

Plethysm is in #BQP
di: Christandl, Matthias, et al.
Pubblicazione: (2026)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
di: Martinsson, Björn
Pubblicazione: (2024)

Extensively Not P-Bi-Immune promiseBQP-Complete Languages
di: Jackson, Andrew
Pubblicazione: (2024)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
di: Iturralde, Paúl Risco
Pubblicazione: (2025)

The 2-Attractor Problem is NP-Complete
di: Fuchs, Janosch, et al.
Pubblicazione: (2023)

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

Determining the Outerthickness of Graphs Is NP-Hard
di: Lee, Pin-Hsian, et al.
Pubblicazione: (2026)

Universal NP-Hardness of Clustering under General Utilities
di: Majumdar, Angshul
Pubblicazione: (2026)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
di: DeJesse, Nicholas, et al.
Pubblicazione: (2025)

Limits of structures and Total NP Search Problems
di: Ježil, Ondřej
Pubblicazione: (2023)

Real Stability and Log Concavity are coNP-Hard
di: Chin, Tracy
Pubblicazione: (2024)

Sorting by Strip Swaps is NP-Hard
di: Roy, Swapnoneel, et al.
Pubblicazione: (2025)

Reducibility among NP-Hard graph problems and boundary classes
di: Hassan, Syed Mujtaba, et al.
Pubblicazione: (2024)

On the Hardness of the Drone Delivery Problem
di: Bartlmae, Simon, et al.
Pubblicazione: (2025)

King Chasing Problem in Chinese Chess is NP-hard
di: Li, Chao, et al.
Pubblicazione: (2026)

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
di: Krebs, Andreas, et al.
Pubblicazione: (2025)

P=NP
di: Deng, Zikang
Pubblicazione: (2024)

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
di: Hair, Isaac M., et al.
Pubblicazione: (2025)

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
di: Pfaue, Femke
Pubblicazione: (2024)

Wataridori is NP-Complete
di: Ruangwises, Suthee
Pubblicazione: (2026)

P vs. NP
di: Uribe, Daniel
Pubblicazione: (2016)

On P Versus NP
di: Gordeev, Lev
Pubblicazione: (2020)

Nondango is NP-Complete
di: Ruangwises, Suthee
Pubblicazione: (2023)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2025)

A Critique of Deng's "P=NP"
di: Humphreys, Isabel, et al.
Pubblicazione: (2025)

Proofs of NP = coNP = PSPACE: Current upgrade
di: Gordeev, Lev, et al.
Pubblicazione: (2023)

On $NP \cap coNP$ proof complexity generators
di: Krajicek, Jan
Pubblicazione: (2025)

Hardness of Hypergraph Edge Modification Problems
di: Gishboliner, Lior, et al.
Pubblicazione: (2025)

Structural Origin and the Minimal Syntax of NP-Hardness: Analysis of SAT from Syntactic Generativity and Compositional Collapse
di: Nishiyama, Yumiko
Pubblicazione: (2025)

BusOut is NP-complete
di: Ishibashi, Takehiro, et al.
Pubblicazione: (2025)

Communication Complexity is NP-hard
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)