Some observations on NP real numbers and P-selective sets

DOI10.1016/0022-0000(81)90068-4zbMath0486.03020OpenAlexW2040131290MaRDI QIDQ1164623

Selman, Alan L.

Publication date: 1981

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90068-4

zbMATH Keywords

NP-hardp-selective setcollapsing hierarchystandard left cut of real numberstally language

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Related Items (11)

On the complexity of kings ⋮ Quasi-linear truth-table reductions to \(p\)-selective sets ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES ⋮ Some results on selectivity and self-reducibility ⋮ On the definitions of some complexity classes of real numbers ⋮ On self-reducibility and weak P-selectivity ⋮ Reducibilities on real numbers ⋮ On symmetric differences of NP-hard sets with weakly P-selective sets

Cites Work

• Reductions on NP and p-selective sets
• A comparison of polynomial time reducibilities
• On the definitions of some complexity classes of real numbers
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Tally languages and complexity classes
• Semirecursive Sets and Positive Reducibility
• Computational Work and Time on Finite Machines
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Some observations on NP real numbers and P-selective sets