scientific article; zbMATH DE number 512798

MaRDI QIDQ4281491zbMATH OpenFDO

Authors Vikraman Arvind, Yenjo Han, Lane A. Hemaspaandra, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Johannes Köbler, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf

Publication date 10 March 1994

zbMATH Keywords

computational complexitylow informationlow instance complexitysparse sets

Mathematics Subject Classification ID

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

Recommendations

• Reductions to sets of low information content (extended abstract)
• Information lower bounds via self-reducibility
• Information Lower Bounds via Self-reducibility
• On the reducibility of sets inside NP to sets with low information content
• scientific article; zbMATH DE number 1333601
• Geometric sets of low information content
• On Degree of Pareto Set Reduction Using Information Quanta

Cited in

(22)

• The structure of logarithmic advice complexity classes
• On reductions of NP sets to sparse sets
• Space-efficient recognition of sparse self-reducible languages
• Geometric sets of low information content
• 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
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• The Power of Self-Reducibility: Selectivity, Information, and Approximation
• Towards the Actual Relationship Between NP and Exponential Time
• scientific article; zbMATH DE number 1333601 (Why is no real title available?)
• Splittings, Robustness, and Structure of Complete Sets
• Fault-tolerance and complexity (extended abstract)
• On sets bounded truth-table reducible to P-selective sets
• Monotonous and randomized reductions to sparse sets
• Upper bounds for the complexity of sparse and tally descriptions
• On sparseness and Turing reducibility over the reals
• Information Lower Bounds via Self-reducibility
• On Degree of Pareto Set Reduction Using Information Quanta
• Reductions to sets of low information content (extended abstract)
• Average-case intractability vs. worst-case intractability
• Dimension, halfspaces, and the density of hard sets

This page was built for publication:

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