Gavaldà, Ricard; Watanabe, Osamu On the computational complexity of small descriptions. (English) Zbl 0799.68085 SIAM J. Comput. 22, No. 6, 1257-1275 (1993). Cited in 4 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.) 68Q25 Analysis of algorithms and problem complexity Keywords:computational complexity; sparse sets; tally sets; polynomial-time reducibility; polynomial-time equivalence; Kolmogorov complexity; circuit complexity PDF BibTeX XML Cite \textit{R. Gavaldà} and \textit{O. Watanabe}, SIAM J. Comput. 22, No. 6, 1257--1275 (1993; Zbl 0799.68085) Full Text: DOI OpenURL