On the Computational Complexity of Small Descriptions

DOI10.1137/0222075MaRDI QIDQ4277541zbMATH OpenOpenAlexFDO

Authors Ricard Gavaldà, Osamu Watanabe

Publication date 13 November 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/191725

zbMATH Keywords

computational complexityKolmogorov complexitycircuit complexitysparse setspolynomial-time reducibilitytally setspolynomial-time equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• On the complexity of small description and related topics
• scientific article; zbMATH DE number 1008507
• The Complexity of Small Universal Turing Machines
• scientific article; zbMATH DE number 17544
• scientific article; zbMATH DE number 4106276
• Small complexity classes for computable analysis
• Descriptive characterizations of computational complexity
• On the power of small-depth computation

Cited in

(14)

• Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
• Upper bounds for the complexity of sparse and tally descriptions
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• On monotonous oracle machines
• Circuit-size lower bounds and non-reducibility to sparse sets
• Reductions to sets of low information content (extended abstract)
• On the complexity of small description and related topics
• Complexity and structure
• scientific article; zbMATH DE number 4160709 (Why is no real title available?)
• All superlinear inverse schemes are coNP-hard
• scientific article; zbMATH DE number 3845567 (Why is no real title available?)
• Small PCPs with low query complexity
• On small generators
• Monotonous and randomized reductions to sparse sets

This page was built for publication: On the Computational Complexity of Small Descriptions

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