Name
Abstract | ||
|---|---|---|
We show that if an NP-complete set or a coNP-complete set is polynomial-time disjunctive truth-table reducible to a sparse
set then FP
∥
NP
= FPNP[log]. Similarly, we show that if SAT is O(log n)-approximable then FP
∥
NP
= FPNP[log]. Since FP
∥
NP
= FPNP[log] implies that SAT is O(log n)-approximable [BFT97], it follows from our result that these two hypotheses are equivalent. We also show that if an NP-complete set or a coNP-complete
set is disjunctively reducible to a sparse set of polylogarithmic density then, in fact, P = NP.
|
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0020-0190(99)00008-3 | STACS'99 Proceedings of the 16th annual conference on Theoretical aspects of computer science |
Keywords | Field | DocType |
computational complexity,polynomial time | Complexity class,Binary logarithm,Discrete mathematics,Combinatorics,NP-complete,Promise problem,Binary search algorithm,True quantified Boolean formula,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
1563 | 4 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-65691-X | 3 | 0.38 |
References | Authors | |
18 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Jacobo Torán | 2 | 564 | 49.26 |