Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0745.68046
Buhrman, Harry; Homer, Steven; Torenvliet, Leen
Completeness for nondeterministic complexity classes. (English)
[J] Math. Syst. Theory 24, No.3, 179-200 (1991). ISSN 0025-5661

Summary: We demonstrate differences between reducibilities and corresponding completeness notions for nondeterministic time and space classes. For time classes the studied completeness notions under polynomial-time bounded (even logarithmic-space bounded) reducibilities turn out to be different for any class containing $NE$. For space classes the completeness notions under logspace reducibilities can be separated for any class properly containing LOGSPACE. Key observation in obtaining the separations is the honesty property of reductions, which was recently observed to hold for the time classes and can be shown to holds for space classes.

MSC 2000:: *68Q15 Complexity classes of computation

Keywords: reducibilities; completeness; nondeterministic time and space classes

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]