
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...)









110 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): 735754, 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 manyone polynomialtime equivalent to each other and to the original set? Thes...

May 30 2007 

The NPcompleteness column Johnson D. ACM Transactions on Algorithms 1(1): 160176, 2005. Type: Article
It has been quite a wait between this last (24th) installment of David Johnson’s NPcompleteness 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 NPPairs Glaser C., Selman A., Sengupta S. (Proceedings of the 19th IEEE Annual Conference on Computational Complexity (CCC’04),Jun 2124, 2004) 4253, 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 Thirtysixth Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, Jun 1316, 2004) 604612, 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): 117138, 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): 12641283, 1999. Type: Article
The property of a problem of being NPcomplete 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 NPcompleteness made easy Crescenzi P., Trevisan L. Theoretical Computer Science 225(12): 6579, 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): 207236, 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 noncompleteness results with respect to readonce projections Bollig B., Wegener I. Information and Computation 143(1): 2433, 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 KarpLevin: separating completeness notions if NP is not small Lutz J., Mayordomo E. Theoretical Computer Science 164(12): 141163, 1996. Type: Article
The notion of NPcompleteness can be defined in two distinct ways. A language can be complete for NP under polynomialtime Turing reducibility (Cook completeness) or under the stronger notion of polynomialtime manyone reducibility (K...

Aug 1 1997 





