Author :
Hemachandra, L. ; Hoene, A. ; Ogiwara, M. ; Selman, A. ; Thierauf, T. ; Wang, J.
Author_Institution :
Dept. of Comput. Sci., Rochester Univ., NY, USA
Abstract :
A set is P-selective if there is a polynomial-time (p-time) semi-decision algorithm for the set-an algorithm that, given any two strings, decides which is “more likely” to be in the set. This paper studies two natural generalizations of P-selectivity: the NP-selective sets and the sets reducible to P-selective sets via p-time reductions. We show that even NP-selective sets are unlikely to be NP-complete, and we establish a strict hierarchy among the various reductions to P-selective sets
Keywords :
computational complexity; decidability; set theory; NP-complete sets; NP-selective se; P-selective sets; P-selectivity; hierarchy; polynomial-time reductions; polynomial-time semi-decision algorithm; strings; Complexity theory; Computer science; Mathematics; Polynomials; Testing;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315404
