Cover Image

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Digulescu, Mircea-Adrian
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

NP-Completeness of Neighborhood Balanced Colorings
by: Asaeedi, Saeed
Published: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

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)

NP-Completeness of Multicast Beamforming in Wireless Communication
by: Shrestha, Sagar
Published: (2025)

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

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

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

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

An Efficient Algorithm for Solving the 2-MAXSAT Problem
by: Chen, Yangjun
Published: (2023)

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

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

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

NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
by: Ruangwises, Suthee
Published: (2024)

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

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

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

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

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

NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam
by: Otsuji, Taisei, et al.
Published: (2026)

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

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
by: Kiatchaipipat, Nattapol, et al.
Published: (2025)

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

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
by: Minevich, Igor, et al.
Published: (2024)

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

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

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
by: Gaikwad, Ajinkya, et al.
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)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, 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)

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

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

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