On Unapproximable Versions of NP-Complete Problems
From MaRDI portal
On Unapproximable Versions of $NP$-Complete Problems
Recommendations
- scientific article; zbMATH DE number 3921977
- A note on non-complete problems in \(NP_\mathbb{R}\)
- scientific article; zbMATH DE number 1775419
- Nonuniform reductions and NP-completeness
- Nonuniform reductions and NP-completeness
- On inefficient special cases of NP-complete problems
- Publication:3484351
- NP-completeness: a retrospective
Cited in
(38)- The hardness of approximation: Gap location
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Two simulated annealing-based heuristics for the job shop scheduling problem
- The inapproximability of non-NP-hard optimization problems.
- MAX3SAT is exponentially hard to approximate if NP has positive dimension.
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Towards optimal lower bounds for clique and chromatic number.
- Counting substrate cycles in topologically restricted metabolic networks
- Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- From typical sequences to typical genotypes
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- scientific article; zbMATH DE number 1670535 (Why is no real title available?)
- The complexity of approximately counting tree homomorphisms
- Approximately counting locally-optimal structures
- Proof verification and the hardness of approximation problems
- Hamming approximation of NP witnesses
- The value of strong inapproximability results for clique
- Approximately Counting Locally-Optimal Structures
- NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k )
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- The complexity of approximately counting stable roommate assignments
- scientific article; zbMATH DE number 1860650 (Why is no real title available?)
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Approximately counting paths and cycles in a graph
- A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations
- Definable inapproximability: new challenges for duplicator
- Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains
- On Some $\mathcal{NP}$ -complete SEFE Problems
- Fast parallel heuristics for the job shop scheduling problem
- Commuting quantum circuits and complexity of Ising partition functions
- The Complexity of Aggregates over Extractions by Regular Expressions
- Shortest path and maximum flow problems in networks with additive losses and gains
- Counting on rainbow k-connections
- The strongish planted clique hypothesis and its consequences
- Inapproximability of the Tutte polynomial
This page was built for publication: On Unapproximable Versions of $NP$-Complete Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5691296)
