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

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