:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Martinsson, Björn
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2408.04832
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

On the Usefulness of Promises
by: Austrin, Per, et al.
Published: (2025)

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

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

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

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

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

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

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

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

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

Hardness of SetCover Reoptimization
by: Jansen, Klaus, et al.
Published: (2025)

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

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)

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

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

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

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

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

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)

P=NP
by: Deng, Zikang
Published: (2024)

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

Improved Hardness Results for Min-Max Optimization with Coupled Constraints
by: Bernasconi, Martino, et al.
Published: (2024)

Training Neural Networks is NP-Hard in Fixed Dimension
by: Froese, Vincent, et al.
Published: (2023)

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

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

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

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

P vs. NP
by: Uribe, Daniel
Published: (2016)

On P Versus NP
by: Gordeev, Lev
Published: (2020)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)

Hardness of Approximate Hylland-Zeckhauser Equilibria
by: Braverman, Mark, et al.
Published: (2026)

BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)

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

On Kernelization with Access to NP-Oracles
by: Molter, Hendrik, et al.
Published: (2025)

Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
by: Binnendyk, Eric
Published: (2025)

Improved Hardness-of-Approximation for Token Swapping
by: Hiken, Sam, et al.
Published: (2024)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$
by: Hecht, Yahli, et al.
Published: (2025)