Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Browse by topic Browse by titles Authors Reviewers Browse by issue Browse Help
  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
Display per page
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy