Reductions on NP and p-selective sets
type: Item
instance of: scholarly article
title: Reductions on NP and p-selective sets
zbMATH Open document ID: 0489.03016
DOI: 10.1016/0304-3975(82)90039-1
published in: Theoretical Computer Science
publication date: 1982-01-01T00:00:00Z
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 3769613
zbMATH Keywords: polynomial time-bounded reducibility
zbMATH Keywords: truth-table reducibility
zbMATH Keywords: positive query machine
zbMATH Keywords: oracle set
author: Alan L. Selman
MaRDI profile type: Publication
full work available at URL: 0304-3975(82)90039-1
OpenAlex ID: W1966945335
cites work: Tally languages and complexity classes
cites work: Inclusion complete tally languages and the Hartmanis-Berman conjecture
cites work: Semirecursive Sets and Positive Reducibility
cites work: The complexity of theorem-proving procedures
cites work: A comparison of polynomial time reducibilities
cites work: On the structure of sets in NP and other complexity classes
cites work: Strong nondeterministic polynomial-time reducibilities
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: The polynomial-time hierarchy
cites work: Relative complexity of checking and evaluating
description: scientific article; zbMATH DE number 3769613