COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Autoreducibility for NEXP

## Autoreducibility for NEXPAdd 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 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}} 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
Note that ex-directory lists are not shown. |
## Other listsType the title of a new list here Denise Schofield Clare Hall Colloquium## Other talksHow to Design a 21st Century Economy - with Kate Raworth The cardinal points and the structure of geographical knowledge in the early twelfth century Geometry and learning in 3D correspondence problems Using Inclusive Design to Focus on User Experience (UX) Immigration and Freedom Revolution and Literature |