✦ LIBER ✦

Dimension in Complexity Classes

✍ Scribed by Lutz, Jack H.

Book ID: 118181158
Publisher: Society for Industrial and Applied Mathematics
Year: 2003
Tongue: English
Weight: 245 KB
Volume: 32
Category: Article
ISSN: 0097-5397
DOI: 10.1137/s0097539701417723

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Dimension Characterizations of Complexit

Dimension Characterizations of Complexity Classes

✍ Xiaoyang Gu; Jack H. Lutz 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 468 KB

Discretized-Vapnik-Chervonenkis Dimensio

Discretized-Vapnik-Chervonenkis Dimension for Analyzing Complexity of Real Function Classes

✍ Zhang, C.; Bian, W.; Tao, D.; Lin, W. 📂 Article 📅 2012 🏛 Institute of Electrical and Electronics Engineers 🌐 English ⚖ 349 KB

Complexity and dimension

✍ Felipe Cucker; Pascal Koiran; Martín Matamala 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 313 KB

Mahaney's Theorem states that there are no sparse NP-complete problems if P # NP. We propose an adaptation of that theorem to the Blum-Shub-Smale model of computation of the reals with addition and equality. In that setting, sparseness is defined in terms of topological dimension instead of cardinal

Comparing complexity classes

✍ Ronald V. Book 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 867 KB

Complexity classes defined by time-bounded and space-bounded Turing acceptors are studied in order to learn more about the cost of deterministic simulation of nondeterministic processes and about time-space tradeoffs. Here complexity classes are compared by means of reducibilities and class-complete

Describing parameterized complexity clas

Describing parameterized complexity classes

✍ Jörg Flum; Martin Grohe 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 323 KB

Logics for complexity classes

✍ Naidenko, V. 📂 Article 📅 2014 🏛 Oxford University Press 🌐 English ⚖ 310 KB