𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Probabilistic complexity classes and lowness

✍ Scribed by Uwe Schöning

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
962 KB
Volume
39
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

New Lowness Results for ZPPNP and Other
New Lowness Results for ZPPNP and Other Complexity Classes
✍ V. Arvind; Johannes Köbler 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 242 KB

We show that the class AM \ coAM is low for ZPP NP . As a consequence, it follows that Graph Isomorphism and several group-theoretic problems are low for ZPP NP . We also show that the class IP½P=poly, consisting of sets that have interactive proof systems with honest provers in P=poly, is also low

The enumerability and invariance of comp
The enumerability and invariance of complexity classes
✍ F.D. Lewis 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 772 KB

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 crite

A low complexity approximation of probab
A low complexity approximation of probabilistic appearance models
✍ Raouf Hamdan; Fabrice Heitz; Laurent Thoraval 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 633 KB

on Computer Vision, Cambridge, MA, June 1995, p. 687; IEEE Trans. Pattern Anal. Mach. Intell. 19 (7) (1997) 696) has recently shown excellent performances in pattern detection and recognition, outperforming most other linear and non-linear approaches. Unfortunately, the complexity of this model rema