𝔖 Bobbio Scriptorium
✦   LIBER   ✦

New Lowness Results for ZPPNP and Other Complexity Classes

✍ Scribed by V. Arvind; Johannes Köbler

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
242 KB
Volume
65
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 for ZPP NP . For the nonuniform function classes NPMV=poly, NPSV=poly, and NPMV t =poly, we show the following lowness results: Sets whose characteristic functions are in NPSV=poly and that have program checkers are low for AM and ZPP NP . Self-reducible sets with characteristic functions in NPMV t =poly are low for S p 2 . Sets whose characteristic functions are in NPMV=poly and that have program checkers are low for S p 2 . We also give applications of these lowness results.

📜 SIMILAR VOLUMES

Undecidability Results for Low Complexit
Undecidability Results for Low Complexity Time Classes
✍ Rod Downey; André Nies 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 165 KB

We prove that the theory of Exptime degrees with respect to polynomial time Turing and many-one reducibility is undecidable. To do so we use a coding method based on ideal lattices of Boolean algebras which was introduced by Nies (1997, Bull. London Math. Soc. 29, 683 692). The method can be applied

The complexity of the matching-cut probl
The complexity of the matching-cut problem for planar graphs and other graph classes
✍ Paul Bonsma 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB

## Abstract The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ${\cal{NP}}$‐complete when restricted to graphs with maximum deg

Diatom motility and low frequency electr
Diatom motility and low frequency electromagnetic fields—A new technique in the search for independent replication of results
✍ N. Clarkson; M.S. Davies; R. Dixey 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

The hypothesis that exposure to a certain combination of static and alternating electromagnetic fields (EMFs) results in an increase in motility of the marine diatom Amphora coffeaeformis was tested. Diatom motility in three strains of A. coffeaeformis was positively correlated with extracellular ca