1996/12/01 by David Zuckerman · 1 citation
Computer Science · Mathematics · #Binary logarithm #Clique #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Counting problem #Discrete mathematics #Exponential time hypothesis #Iterated function #Law of the iterated logarithm #Logarithm #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Mathematics #Monotone polygon #Polynomial #Randomized algorithm #Simple (philosophy) #Time complexity
paper · doi:10.1137/s0097539794266407
openalex publication_date 1996/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
We prove that all of Karp’s 21 original NP-complete problems have a version that is hard to approximate. These versions are obtained from the original problems by adding essentially the same simple constraint. We further show that these problems are absurdly hard to approximate. In fact, no polynomial-time algorithm can even approximate log (k) of the magnitude of these problems to within any constant factor, where log (k) denotes the logarithm iterated k times, unless NP is recognized by slightly superpolynomial randomized machines. We use the same technique to improve the constant ε such that MAX CLIQUE is hard to approximate to within a factor of nε . Finally, we show that it is even harder to approximate two counting problems: counting the number of satisfying assignments to a monotone 2SAT formula and computing the permanent of - 1,0,1 matrices.