Pages that link to "Item:Q5691296"
From MaRDI portal
The following pages link to On Unapproximable Versions of $NP$-Complete Problems (Q5691296):
Displaying 36 items.
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region (Q269470) (← links)
- Approximately counting locally-optimal structures (Q295655) (← links)
- The complexity of approximately counting stable roommate assignments (Q440007) (← links)
- Approximately counting paths and cycles in a graph (Q516844) (← links)
- Shortest path and maximum flow problems in networks with additive losses and gains (Q620954) (← links)
- Inapproximability of the Tutte polynomial (Q937302) (← links)
- The hardness of approximation: Gap location (Q1332662) (← links)
- Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
- Two simulated annealing-based heuristics for the job shop scheduling problem (Q1806614) (← links)
- Taking it to the limit: On infinite variants of NP-complete problems (Q1816727) (← links)
- The inapproximability of non-NP-hard optimization problems. (Q1853546) (← links)
- MAX3SAT is exponentially hard to approximate if NP has positive dimension. (Q1853564) (← links)
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. (Q1854505) (← links)
- Towards optimal lower bounds for clique and chromatic number. (Q1874411) (← links)
- Counting substrate cycles in topologically restricted metabolic networks (Q2011645) (← links)
- Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs (Q2308511) (← links)
- Constructing NP-intermediate problems by blowing holes with parameters of various properties (Q2345449) (← links)
- From typical sequences to typical genotypes (Q2402303) (← links)
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz (Q2632506) (← links)
- Complexity and approximability of quantified and stochastic constraint satisfaction problems (Q2741527) (← links)
- On the hardness of approximating \({\mathcal N}{\mathcal P}\) witnesses (Q2753732) (← links)
- The Complexity of Approximately Counting Tree Homomorphisms (Q2943573) (← links)
- Proof verification and the hardness of approximation problems (Q3158513) (← links)
- Hamming Approximation of NP Witnesses (Q3191592) (← links)
- Approximately Counting Locally-Optimal Structures (Q3448823) (← links)
- NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k ) (Q3507322) (← links)
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP (Q3608306) (← links)
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More (Q5115701) (← links)
- A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations (Q5215456) (← links)
- Definable inapproximability: new challenges for duplicator (Q5216336) (← links)
- Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains (Q5321689) (← links)
- On Some $\mathcal{NP}$ -complete SEFE Problems (Q5746258) (← links)
- Fast parallel heuristics for the job shop scheduling problem (Q5955476) (← links)
- Commuting quantum circuits and complexity of Ising partition functions (Q6100591) (← links)
- The Complexity of Aggregates over Extractions by Regular Expressions (Q6135782) (← links)
- Counting on rainbow \(k\)-connections (Q6636091) (← links)