Reductions on NP and p-selective sets
From MaRDI portal
Publication:1166515
DOI10.1016/0304-3975(82)90039-1zbMath0489.03016OpenAlexW1966945335MaRDI QIDQ1166515
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90039-1
Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (49)
The complexity of online bribery in sequential elections ⋮ A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ Bi-immunity separates strong NP-completeness notions ⋮ On the complexity of kings ⋮ Quasi-linear truth-table reductions to \(p\)-selective sets ⋮ Reductions between disjoint NP-pairs ⋮ Promise problems complete for complexity classes ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ On closure properties of bounded two-sided error complexity classes ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Positive relativizations of the \(P=?\) NP problem ⋮ On monotonous oracle machines ⋮ Promise problems and access to unambiguous computation ⋮ Characterizations of reduction classes modulo oracle conditions ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ P-immune sets with holes lack self-reducibility properties. ⋮ Query complexity of membership comparable sets. ⋮ A note on degrees of presentation of games as relational structures ⋮ Robust machines accept easy sets ⋮ Unnamed Item ⋮ Some observations on NP real numbers and P-selective sets ⋮ On membership comparable sets ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ An NL hierarchy ⋮ ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Reducibility classes of P-selective sets ⋮ Some results on selectivity and self-reducibility ⋮ P-selectivity: Intersections and indices ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Dot operators ⋮ Non-mitotic Sets ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Hard promise problems and nonuniform complexity ⋮ Probabilistic complexity classes and lowness ⋮ Non-mitotic sets ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ The Complexity of Reasoning for Fragments of Default Logic ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ On the computational complexity of best Chebyshev approximations ⋮ Complete sets and closeness to complexity classes ⋮ SELF-SPECIFYING MACHINES ⋮ On self-reducibility and weak P-selectivity ⋮ Strong nondeterministic polynomial-time reducibilities ⋮ On symmetric differences of NP-hard sets with weakly P-selective sets ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
Cites Work
- Strong nondeterministic polynomial-time reducibilities
- On the structure of sets in NP and other complexity classes
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Tally languages and complexity classes
- Semirecursive Sets and Positive Reducibility
- The complexity of theorem-proving procedures
This page was built for publication: Reductions on NP and p-selective sets
