Completeness for nondeterministic complexity classes |
| |
Authors: | Harry Buhrman Steven Homer Leen Torenvliet |
| |
Affiliation: | (1) Departments of Mathematics and Computer Science, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands;(2) Computer Science Department, Boston University, 02215 Boston, MA, USA |
| |
Abstract: | 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 containingNE. For space classes the completeness notions under logspace reducibilities can be separated for any class properly containingLOGSPACE. 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 hold for space classes.The work of S. Homer was supported in part by National Science Foundation Grants MIP-8608137 and CCR-8814339 and a Fulbright-Hays Research Fellowship. Some of this research was done while he was a Guest Professor at the Mathematics Institute of Heidelberg University. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|