On polynomial-time truth-table reducibility of intractable sets to P-selective sets
From MaRDI portal
Publication:3210177
Recommendations
Cites work
- scientific article; zbMATH DE number 3984573 (Why is no real title available?)
- scientific article; zbMATH DE number 3594673 (Why is no real title available?)
- A Note on Sparse Complete Sets
- A low and a high hierarchy within NP
- A note on sparse oracles for NP
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Complete sets and the polynomial-time hierarchy
- Complexity Measures for Public-Key Cryptosystems
- Computational Complexity of Probabilistic Turing Machines
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- NP is as easy as detecting unique solutions
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On Restricting the Size of Oracles Compared with Restricting Access to Oracles
- On Sets Truth-Table Reducible to Sparse Sets
- On hardness of one-way functions
- On self-reducibility and weak P-selectivity
- On the Computational Complexity of Algorithms
- Polynomial terse sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Reductions on NP and p-selective sets
- Relative complexity of checking and evaluating
- Some consequences of non-uniform conditions on uniform classes
- Some observations on NP real numbers and P-selective sets
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Tally languages and complexity classes
- The complexity of promise problems with applications to public-key cryptography
- The polynomial-time hierarchy
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
Cited in
(29)- On the complexity of data disjunctions.
- Optimal series-parallel trade-offs for reducing a function to its own graph
- On the reducibility of sets inside NP to sets with low information content
- The complexity of finding top-Toda-equivalence-class members
- Structural analysis of the complexity of inverse functions
- Quasi-linear truth-table reductions to \(p\)-selective sets
- One query reducibilities between partial information classes
- Query complexity of membership comparable sets.
- On symmetric differences of NP-hard sets with weakly P-selective sets
- Polynomial-Time Membership Comparable Sets
- \(p\)-Selective sets and reducing search to decision vs. self-reducibility
- A taxonomy of complexity classes of functions
- Adaptive versus nonadaptive queries to NP and P-selective sets
- NP-hard sets are superterse unless NP is small
- scientific article; zbMATH DE number 1414313 (Why is no real title available?)
- Approximable sets
- Computing functions with parallel queries to NP
- Small space analogues of Valiant's classes and the limitations of skew formulas
- On sets bounded truth-table reducible to $P$-selective sets
- Counting classes: Thresholds, parity, mods, and fewness
- scientific article; zbMATH DE number 2097995 (Why is no real title available?)
- Robustness of PSPACE-complete sets
- LATIN 2004: Theoretical Informatics
- On membership comparable sets
- On sets Turing reducible to p-selective sets
- Monotonous and randomized reductions to sparse sets
- Some structural properties of SAT
- Reducibility classes of P-selective sets
- Some results on selectivity and self-reducibility
This page was built for publication: On polynomial-time truth-table reducibility of intractable sets to P-selective sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3210177)
