On polynomial-time truth-table reducibility of intractable sets to P-selective sets

DOI10.1007/BF02090391zbMath0722.68059OpenAlexW1967283546MaRDI QIDQ3210177

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

zbMATH Keywords

reducibilitypolynomial-time hierarchylow setsnonpositive reducibilities

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A taxonomy of complexity classes of functions, NP-hard sets are superterse unless NP is small, Robustness of PSPACE-complete sets, Quasi-linear truth-table reductions to \(p\)-selective sets, Structural analysis of the complexity of inverse functions, Query complexity of membership comparable sets., Small space analogues of Valiant's classes and the limitations of skew formulas, On membership comparable sets, Reducibility classes of P-selective sets, Some results on selectivity and self-reducibility, Computing functions with parallel queries to NP, On sets Turing reducible to p-selective sets, Counting classes: Thresholds, parity, mods, and fewness, On the reducibility of sets inside NP to sets with low information content, On sets bounded truth-table reducible to $P$-selective sets, Monotonous and randomized reductions to sparse sets, Some structural properties of SAT, On the complexity of data disjunctions., Optimal series-parallel trade-offs for reducing a function to its own graph, On symmetric differences of NP-hard sets with weakly P-selective sets

Cites Work

• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• A low and a high hierarchy within NP
• On self-reducibility and weak P-selectivity
• NP is as easy as detecting unique solutions
• On hardness of one-way functions
• Polynomial terse sets
• Some observations on NP real numbers and P-selective sets
• A note on sparse oracles for NP
• Reductions on NP and p-selective sets
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A Note on Sparse Complete Sets
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On Circuit-Size Complexity and the Low Hierarchy in NP
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• The complexity of promise problems with applications to public-key cryptography
• Complexity Measures for Public-Key Cryptosystems
• On Sets Truth-Table Reducible to Sparse Sets
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Inclusion complete tally languages and the Hartmanis-Berman conjecture
• Computational Complexity of Probabilistic Turing Machines
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Tally languages and complexity classes
• On the Computational Complexity of Algorithms