✦ LIBER ✦

The enumerability and invariance of complexity classes

✍ Scribed by F.D. Lewis

Publisher: Elsevier Science
Year: 1971
Tongue: English
Weight: 772 KB
Volume: 5
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(71)80037-5

No coin nor oath required. For personal study only.

✦ Synopsis

Several properties of complexity classes and sets associated with them are studied. An open problem, the enumerability of complexity classes, is settled by exhibition of a measure with some nonenumerable classes. Classes for natural measures are found to occupy the same isomorphism type; and a criterion for measures comes from this finding. General results about measures and unsolvability are presented and constraints are placed on complexity classes so that they possess identical properties.

📜 SIMILAR VOLUMES

The enumeration of lie invariants

✍ M. D. Burrow 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 431 KB

The complexity of model classes, and smo

The complexity of model classes, and smoothing noisy data

✍ Peter L Bartlett; Sanjeev R Kulkarni 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 118 KB

Karp complexity and classes with the ind

Karp complexity and classes with the independence property

✍ M.C. Laskowski; S. Shelah 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 216 KB

A class K of structures is controlled if for all cardinals , the relation of L ∞; -equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that no pseudo-elementary class with the independence property is controlled. By contrast, there is a pseudo-elementa

A characterization of the class of enume

A characterization of the class of enumerable languages

✍ K. K. Pivnitskaya 📂 Article 📅 1992 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 482 KB

Classes of recursively enumerable sets a

Classes of recursively enumerable sets and Q-reducibility

✍ R. Sh. Omanadze 📂 Article 📅 1989 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 205 KB

The Communication Complexity of Enumerat

The Communication Complexity of Enumeration, Elimination, and Selection

✍ Andris Ambainis; Harry Buhrman; William Gasarch; Bala Kalyanasundaram; Leen Tore 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 278 KB

Let k, n ¥ N and f: {0, 1} n × {0, 1} n Q {0, 1}. Assume Alice has x 1 , ..., x k ¥ {0, 1} n , Bob has y 1 , ..., y k ¥ {0, 1} n , and they want to compute municating as few bits as possible. The direct sum conjecture (henceforth DSC) n (log log(n))(log(n)) ) bits. This establishes a weak randomize