Some results on selectivity and self-reducibility
type: Item
instance of: scholarly article
title: Some results on selectivity and self-reducibility
zbMATH Open document ID: 0875.68423
DOI: 10.1016/0020-0190(95)00073-L
author: Jie Wang
published in: Information Processing Letters
publication date: 1997-02-28T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 984969
zbMATH Keywords: Complexity classes
zbMATH Keywords: Self-reducibility
zbMATH Keywords: Selectivity
zbMATH Keywords: P
zbMATH Keywords: NP
zbMATH Keywords: PP
MaRDI profile type: Publication
cites work: Q4039803
cites work: Adaptive versus nonadaptive queries to NP and P-selective sets
cites work: PP is closed under truth-table reductions
cites work: Computing Solutions Uniquely Collapses the Polynomial Hierarchy
cites work: Semirecursive Sets and Positive Reducibility
cites work: On self-reducibility and weak P-selectivity
cites work: Strong nondeterministic polynomial-time reducibilities
cites work: Polynomial-Time Membership Comparable Sets
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: Some observations on NP real numbers and P-selective sets
cites work: Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
cites work: Reductions on NP and p-selective sets
cites work: On polynomial-time truth-table reducibility of intractable sets to P-selective sets
Recommended article: The Power of Self-Reducibility: Selectivity, Information, and Approximation
Recommended article: \(p\)-selective self-reducible sets: a new characterization of P
Recommended article: \(p\)-Selective sets and reducing search to decision vs. self-reducibility
Recommended article: Q3765251
Recommended article: Self-reducibility
Recommended article: Q4931969
Recommended article: Q4675732
Recommended article: Intrinsic Reducibilities
Recommended article: Q3972119
Recommended article: Reduction principles in the theory of selections
description: scientific article; zbMATH DE number 984969