scientific article; zbMATH DE number 512798
From MaRDI portal
Publication:4281491
zbMath0794.68058MaRDI QIDQ4281491
Martin Mundhenk, Antoni Lozano, Hemaspaandra, Lane A., Mitsunori Ogiwara, V. Arvind, Yenjo Han, Riccardo Silvestri, Thomas Thierauf, Johannes Köbler, Uwe Schoening
Publication date: 10 March 1994
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (17)
On reductions of NP sets to sparse sets ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ Geometric sets of low information content ⋮ Average-case intractability vs. worst-case intractability ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Dimension, halfspaces, and the density of hard sets ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ On sparseness and Turing reducibility over the reals ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ On sparseness, reducibilities, and complexity ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ The structure of logarithmic advice complexity classes ⋮ Towards the Actual Relationship Between NP and Exponential Time
This page was built for publication:
