Reductions to sets of low information content (extended abstract)

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

Recommendations

scientific article; zbMATH DE number 512798
Upper bounds for the complexity of sparse and tally descriptions
scientific article; zbMATH DE number 1318517
Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

Cites work

\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
A comparison of polynomial time reducibilities
A note on enumerative counting
A Note on Sparse Complete Sets
Bounded Query Classes
Counting classes: Thresholds, parity, mods, and fewness
Distinguishing conjunctive and disjunctive reducibilities by sparse sets
Enumeration of lozenge tilings of a hexagon with a shamrock missing on the symmetry axis
scientific article; zbMATH DE number 4100610 (Why is no real title available?)
scientific article; zbMATH DE number 4106273 (Why is no real title available?)
scientific article; zbMATH DE number 48150 (Why is no real title available?)
scientific article; zbMATH DE number 3594673 (Why is no real title available?)
scientific article; zbMATH DE number 1318517 (Why is no real title available?)
scientific article; zbMATH DE number 4001485 (Why is no real title available?)
Instance complexity
On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
On intractability of the classUP
On Isomorphisms and Density of NP and Other Complete Sets
On reductions of NP sets to sparse sets
On relativized exponential and probabilistic complexity classes
On Sets Truth-Table Reducible to Sparse Sets
On Sets with Efficient Implicit Membership Tests
On the Computational Complexity of Small Descriptions
On the power of parity polynomial time
Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Relating Equivalence and Reducibility to Sparse Sets
Relativizing relativized computations
Some connections between bounded query classes and non-uniform complexity.
Some consequences of non-uniform conditions on uniform classes
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
The Boolean Hierarchy I: Structural Properties
The Boolean Hierarchy II: Applications
The isomorphism conjecture fails relative to a random oracle
Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

Cited in

(12)

Geometric sets of low information content
On the reducibility of sets inside NP to sets with low information content
Characterizations and existence of easy sets without hard subsets
Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
The Power of Self-Reducibility: Selectivity, Information, and Approximation
About the Lossless Reduction of the Minimal Generator Family of a Context
scientific article; zbMATH DE number 1333601 (Why is no real title available?)
scientific article; zbMATH DE number 512798 (Why is no real title available?)
scientific article; zbMATH DE number 1008510 (Why is no real title available?)
Upper bounds for the complexity of sparse and tally descriptions
Information Lower Bounds via Self-reducibility
On Degree of Pareto Set Reduction Using Information Quanta

This page was built for publication: Reductions to sets of low information content (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204315)