The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
On Unapproximable Versions of $NP$-Complete Problems
David Zuckerman,
Pages. 1293-1304
Abstract
Contents 1. Introduction
1.1. Previous work
1.2. A new rold for old reductions
1.3. The small jump to unapproximability
1.4. Hyperunapproximability results
1.5. Implications for counting problems
2. The iterated log of max clique is hard to approximate
3. Unapproximable versions of $NP$-complete problems
4. Two unapproximable counting problems
Key words $NP$-complete, unapproximable, randomized reduction, clique counting problems, permanent, 2SAT.
Mathmatical Subject Classification 68Q15, 68Q25, 68Q99