Sign in
Back
Reducibility classes of P-selective sets
Journal article   Open access  Peer reviewed

Reducibility classes of P-selective sets

Lane A Hemaspaandra, Albrecht Hoene and Mitsunori Ogihara
Theoretical computer science, Vol.155(2), pp.447-457
1996-01-01
DOI: https://doi.org/10.1016/0304-3975(96)00094-1

Abstract

A set is P-selective (Selman, 1979) if there is a polynomial-time semidecision algorithm for the set - an algorithm that given any two strings decides which is 'more likely' to be in the set. This paper establishes a strict hierarchy among the various reductions and equivalences to P-selective sets.
url
https://doi.org/10.1016/0304-3975(96)00094-1View
Published (Version of record) Open

Metrics

2 Record Views
6 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
4 Electrical Engineering, Electronics & Computer Science
4.182 Data Structures, Algorithms & Complexity
4.182.1226 Computability
Web Of Science research areas
Computer Science, Theory & Methods
ESI research areas
Computer Science

UN Sustainable Development Goals (SDGs)

This output has contributed to the advancement of the following goals:

undefined

Source: InCites

Details