Reductions to sets of low information content
From MaRDI portal
Publication:5204315
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
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
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