| |
Browse All Reviews > Theory Of Computation (F) > Computation By Abstract Devices (F.1) > Complexity Measures And Classes (F.1.3) > Reducibility And Completeness (F.1.3...)
|
|
 |
|
|
| |
|
|
| |
1-10 of 37
Reviews about "Reducibility And Completeness (F.1.3...)":
|
Date Reviewed |
| |
Autoreducibility, mitoticity, and immunity
Glaßer C., Ogihara M., Pavan A., Selman A., Zhang L. Journal of Computer and System Sciences 73(5): 735-754, 2007. Type: Article
Can one quickly test whether an element is in a set by asking whether a different element is in the set? Can sets be split into two parts, each of which is many-one polynomial-time equivalent to each other and to the original set? Thes...
|
May 30 2007 |
| |
 The NP-completeness column
Johnson D. ACM Transactions on Algorithms 1(1): 160-176, 2005. Type: Article
It has been quite a wait between this last (24th) installment of David Johnson’s NP-completeness column and the 23rd [1], which came out in 1992. This one is the first to appear in the new journal ACM Transactions on Algor...
|
Aug 4 2006 |
| |
Reductions between Disjoint NP-Pairs
Glaser C., Selman A., Sengupta S. (Proceedings of the 19th IEEE Annual Conference on Computational Complexity (CCC’04),Jun 21-24, 2004) 42-53, 2004. Type: Proceedings
One theme in complexity theory is to show that seemingly different, interesting questions in fact stand or fall together. This paper skillfully does that for the issue of whether complete disjoint nondeterministic polynomial (NP) pairs...
|
Jan 4 2005 |
| |
The complexity of pure Nash equilibria
Fabrikant A., Papadimitriou C., Talwar K. Annual ACM Symposium on Theory of Computing (Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, Jun 13-16, 2004) 604-612, 2004. Type: Proceedings
A relatively new research area in theoretical computer science, at the intersection of game theory and computer science, is brought to light in this paper. The problem of computing pure Nash equilibria (PNE) is discussed, and specific ...
|
Sep 3 2004 |
| |
Reducing the complexity of reductions
Agrawal M., Allender E., Impagliazzo R., Pitassi T., Rudich S. Computational Complexity 10(2): 117-138, 2002. Type: Article
The authors investigate separations and collapses in the power of reductions, in terms of their making sets complete for classes, and the stronger results implicit in certain types of completeness....
|
Nov 22 2002 |
| |
Distributional word problem for groups
Wang J. SIAM Journal on Computing 28(4): 1264-1283, 1999. Type: Article
The property of a problem of being NP-complete means only that there are some instances of the problem that are hard to solve (unless, of course, P = N P ). It leaves open the possibility that such instances are unco...
|
Jul 1 2000 |
| |
Max NP-completeness made easy
Crescenzi P., Trevisan L. Theoretical Computer Science 225(1-2): 65-79, 1999. Type: Article
Two approaches have been devised to study and understand the approximability (or lack thereof) of NP optimization problems: the computational and the syntactic. The computational approach considers the classes APX and PTAS of problems ...
|
Mar 1 2000 |
| |
Succinct representation, leaf languages, and projection reductions
Veith H. Information and Computation 142(2): 207-236, 1998. Type: Article
Problems that are complete for complexity classes usually turn outto be complete under very restrictive types of reducibility. Althoughthis has frequently been observed informally, only very recently hasthere been work proving that thi...
|
Aug 1 1999 |
| |
Completeness and non-completeness results with respect to read-once projections
Bollig B., Wegener I. Information and Computation 143(1): 24-33, 1998. Type: Article
Representations of Boolean functions using restricted types of binary decision diagrams are popular in automated verification. This paper is concerned with reductions among computational problems that are appropriate for these kinds of...
|
Jun 1 1999 |
| |
Cook versus Karp-Levin: separating completeness notions if NP is not small
Lutz J., Mayordomo E. Theoretical Computer Science 164(1-2): 141-163, 1996. Type: Article
The notion of NP-completeness can be defined in two distinct ways. A language can be complete for NP under polynomial-time Turing reducibility (Cook completeness) or under the stronger notion of polynomial-time many-one reducibility (K...
|
Aug 1 1997 |
| |
|
|
| |
|
|
