P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
From MaRDI portal
Publication:4190619
DOI10.1007/BF01744288zbMath0405.03018MaRDI QIDQ4190619
Publication date: 1979
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (60)
A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ NP-hard sets are superterse unless NP is small ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ A note on complete problems for complexity classes ⋮ On the complexity of kings ⋮ Robustness of PSPACE-complete sets ⋮ Quasi-linear truth-table reductions to \(p\)-selective sets ⋮ On resource-bounded instance complexity ⋮ Query-monotonic Turing reductions ⋮ Reductions between disjoint NP-pairs ⋮ Diagonalizations over polynomial time computable sets ⋮ Promise problems complete for complexity classes ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ Is Valiant-Vazirani's isolation probability improvable? ⋮ Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ Time bounded frequency computations ⋮ Dimension and the structure of complexity classes ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ The Shrinking Property for NP and coNP ⋮ Query complexity of membership comparable sets. ⋮ The shrinking property for NP and coNP ⋮ The join can lower complexity ⋮ Robust machines accept easy sets ⋮ A uniform approach to obtain diagonal sets in complexity classes ⋮ Some observations on NP real numbers and P-selective sets ⋮ Reductions on NP and p-selective sets ⋮ On membership comparable sets ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ 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 ⋮ On quasilinear-time complexity theory ⋮ Some results on selectivity and self-reducibility ⋮ Optimal advice ⋮ P-selectivity: Intersections and indices ⋮ A note on P-selective sets and closeness ⋮ On sets Turing reducible to p-selective sets ⋮ The complexity of unions of disjoint sets ⋮ Sparse selfreducible sets and nonuniform lower bounds ⋮ Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998 ⋮ SOME INITIAL THOUGHTS ON BOUNDED QUERY COMPUTATIONS OVER THE REALS ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Non-mitotic Sets ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Hard promise problems and nonuniform complexity ⋮ Non-mitotic sets ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ A hierarchy based on output multiplicity ⋮ Boolean operations, joins, and the extended low hierarchy ⋮ On self-reducibility and weak P-selectivity ⋮ One query reducibilities between partial information classes ⋮ Resource bounded immunity and simplicity ⋮ Optimal series-parallel trade-offs for reducing a function to its own graph ⋮ Padding, commitment and self-reducibility ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
Cites Work
- A comparison of polynomial time reducibilities
- Comparing complexity classes
- Every Prime Has a Succinct Certificate
- On the Structure of Polynomial Time Reducibility
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- Tally languages and complexity classes
- Turing machines and the spectra of first-order formulas
- Semirecursive Sets and Positive Reducibility
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- On Languages Accepted in Polynomial Time
- The complexity of theorem-proving procedures
This page was built for publication: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
