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
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
