On polynomial-time truth-table reducibility of intractable sets to P-selective sets
From MaRDI portal
Publication:3210177
DOI10.1007/BF02090391zbMATH Open0722.68059OpenAlexW1967283546MaRDI QIDQ3210177FDOQ3210177
Authors: Seinosuke Toda 
Publication date: 1991
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02090391
Recommendations
Cites Work
- On the Computational Complexity of Algorithms
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The polynomial-time hierarchy
- Title not available (Why is that?)
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Computational Complexity of Probabilistic Turing Machines
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Complexity Measures for Public-Key Cryptosystems
- NP is as easy as detecting unique solutions
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- The complexity of promise problems with applications to public-key cryptography
- Some consequences of non-uniform conditions on uniform classes
- On self-reducibility and weak P-selectivity
- A low and a high hierarchy within NP
- Relative complexity of checking and evaluating
- Complete sets and the polynomial-time hierarchy
- A Note on Sparse Complete Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Tally languages and complexity classes
- On hardness of one-way functions
- Reductions on NP and p-selective sets
- Polynomial terse sets
- Some observations on NP real numbers and P-selective sets
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Title not available (Why is that?)
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- A note on sparse oracles for NP
- On Sets Truth-Table Reducible to Sparse Sets
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- On Restricting the Size of Oracles Compared with Restricting Access to Oracles
Cited In (28)
- 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
- Structural analysis of the complexity of inverse functions
- The complexity of finding top-Toda-equivalence-class members
- 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
- Adaptive versus nonadaptive queries to NP and P-selective sets
- A taxonomy of complexity classes of functions
- Title not available (Why is that?)
- NP-hard sets are superterse unless NP is small
- Approximable sets
- Computing functions with parallel queries to NP
- On sets bounded truth-table reducible to $P$-selective sets
- Small space analogues of Valiant's classes and the limitations of skew formulas
- Counting classes: Thresholds, parity, mods, and fewness
- Title not available (Why is that?)
- 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)
