Autoreducibility for NEXP

Add to your list(s) Download to your calendar using vCal

• Nguyen, D (University at Buffalo)
• Wednesday 04 July 2012, 12:00-12:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

Autoreducibility was first introduced by Trakhtenbrot in a recursion theoretic setting. A set $A$ is autoreducible if there is an oracle Turing machine $M$ such that $A = L(M^{A)$ and M never queries $x$ on input $x$. Ambos-Spies introduced the polynomial-time variant of autoreducibility, where we require the oracle Turing machine to run in polynomial time.}

The question of whether complete sets for various classes are polynomial-time autoreducible has been studied extensively. In some cases, it turns out that resolving autoreducibility can result in interesting complexity class separations. One question that remains open is whether all Turing complete sets for NEXP are Turing autoreducible. An important separation may result when solving the autoreducibility for NEXP ; if there is one Turing complete set of NEXP that is not Turing autoreducible, then EXP is different from NEXP . We do not know whether proving all Turing complete sets of NEXP are Turing autoreducible yields any separation results.

Buhrman et al. showed that all ${le_{mathit{2mbox{-}tt}}{mathit{p}}}$-complete sets for EXP are ${le_{mathit{2mbox{-}tt}}^{}}$-autoreducible. This proof technique exploits the fact that EXP is closed under exponential-time reductions that only ask one query that is smaller in length. Difficulties arise when we want to prove that the above result holds for NEXP , because we do not know whether this property still holds for NEXP . To resolve that difficulty, we use a nondeterministic technique that applies to NEXP and obtain the similar result for NEXP ; that is, all ${le_{mathit{2mbox{-}tt}}}{mathit{p}}}$-complete sets for NEXP are ${le_{mathit{2mbox{-}tt}}^{}}$-autoreducible. Using similar techniques, we can also show that every disjunctive and conjunctive truth-table complete set for NEXP is disjunctive and conjunctive truth-table autoreducible respectively. In addition to those positive results, negative ones are also given. Using different notions of reductions, we can show that there is a complete set for NEXP that is not autoreducible. Finally, in the relativized world, there is a ${le_{mathit{2mbox{-}T}}}{mathit{p}}}$-complete set for NEXP that is not Turing autoreducible.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.