✦ LIBER ✦

Undecidability Results for Low Complexity Time Classes

✍ Scribed by Rod Downey; André Nies

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 165 KB
Volume: 60
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1999.1678

No coin nor oath required. For personal study only.

✦ Synopsis

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, in fact, to all time classes given by a time constructible function which dominates all polynomials. By a similar method, we construct an oracle U such that Th(NP U , ) is undecidable.

📜 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

Rapid separation and immunoassay for low

Rapid separation and immunoassay for low levels of Salmonella in foods using magnetosome–antibody complex and real-time fluorescence quantitative PCR

✍ Aihua Li; Huiyuan Zhang; Xin Zhang; Qi Wang; Jiesheng Tian; Ying Li; Jilun Li 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 1 views

## Abstract A rapid and economical method for detecting __Salmonella__ was developed, based on a novel complex for immunomagnetic separation, which was composed of anti‐__Salmonella__ polyclonal antibody (Ab) and magnetosome (bacterial magnetic particle, BMP) produced by the bacterium __Magnetospir