On the Computational Complexity of Small Descriptions
From MaRDI portal
Publication:4277541
DOI10.1137/0222075zbMath0799.68085OpenAlexW1967862312MaRDI QIDQ4277541
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
computational complexityKolmogorov complexitycircuit complexitysparse setspolynomial-time reducibilitytally setspolynomial-time equivalence
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
On monotonous oracle machines ⋮ On the complexity of small description and related topics ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Reductions to sets of low information content ⋮ Monotonous and randomized reductions to sparse sets ⋮ All superlinear inverse schemes are coNP-hard
This page was built for publication: On the Computational Complexity of Small Descriptions
