On self-reducibility and weak P-selectivity
type: Item
instance of: scholarly article
title: On self-reducibility and weak P-selectivity
zbMATH Open document ID: 0519.68062
DOI: 10.1016/0022-0000(83)90013-2
published in: Journal of Computer and System Sciences
publication date: 1983-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 3823148
zbMATH Keywords: NP
zbMATH Keywords: self-reducibility
zbMATH Keywords: lowness
zbMATH Keywords: P-selective sets
zbMATH Keywords: left Dedekind cuts
zbMATH Keywords: polynomial-time m-completeness
zbMATH Keywords: polynomial-time T-completeness
author: Ker-I Ko
MaRDI profile type: Publication
full work available at URL: 0022-0000(83)90013-2
OpenAlex ID: W2069139349
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Some lowness properties and computational complexity sequences
cites work: Q4185802
cites work: Q4160434
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Q4138187
cites work: A Note on Sparse Complete Sets
cites work: The maximum value problem and NP real numbers
cites work: On Circuit-Size Complexity and the Low Hierarchy in NP
cites work: Completeness, Approximation and Density
cites work: A comparison of polynomial time reducibilities
cites work: Q5573961
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: Reductions on NP and p-selective sets
cites work: Computational complexity, speedable and levelable sets
cites work: Q4131648
description: scientific article; zbMATH DE number 3823148