Reductions to sets of low information content

DOI10.1007/3-540-55719-9_72zbMath1425.68125OpenAlexW2134249187MaRDI QIDQ5204315

Yenjo Han, Hemaspaandra, Lane A., V. Arvind, Mitsunori Ogiwara, Martin Mundhenk, Antoni Lozano, Riccardo Silvestri, Uwe Schoening, Johannes Köbler, Thomas Thierauf

Publication date: 4 December 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55719-9_72

zbMATH Keywords

sparse setspolynomial hierarchycomplexity theoryTuring reduction

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• A note on enumerative counting
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• A comparison of polynomial time reducibilities
• On reductions of NP sets to sparse sets
• Some connections between bounded query classes and non-uniform complexity.
• Enumeration of lozenge tilings of a hexagon with a shamrock missing on the symmetry axis
• Relativizing relativized computations
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• A Note on Sparse Complete Sets
• On intractability of the classUP
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Bounded Query Classes
• On relativized exponential and probabilistic complexity classes
• On Sets Truth-Table Reducible to Sparse Sets
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On Sets with Efficient Implicit Membership Tests
• Relating Equivalence and Reducibility to Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the Computational Complexity of Small Descriptions
• Instance complexity
• The isomorphism conjecture fails relative to a random oracle
• On the power of parity polynomial time
• Counting classes: Thresholds, parity, mods, and fewness

This page was built for publication: Reductions to sets of low information content