DocumentCode
1988882
Title
Selectivity
Author
Hemachandra, L. ; Hoene, A. ; Ogiwara, M. ; Selman, A. ; Thierauf, T. ; Wang, J.
Author_Institution
Dept. of Comput. Sci., Rochester Univ., NY, USA
fYear
1993
fDate
27-29 May 1993
Firstpage
55
Lastpage
59
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location
Sudbury, Ont.
Print_ISBN
0-8186-4212-2
Type
conf
DOI
10.1109/ICCI.1993.315404
Filename
315404
Link To Document