BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Autoreducibility for NEXP - Nguyen\, D (University at Buffalo)
DTSTART:20120704T110000Z
DTEND:20120704T113000Z
UID:TALK38845@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:\nAutoreducibility was first introduced by Trakhtenbrot in a r
 ecursion\ntheoretic setting. A set $A$ is autoreducible if there is an ora
 cle\nTuring machine $M$ such that $A = L(M^A)$ and M never queries $x$\non
  input $x$. Ambos-Spies introduced the polynomial-time variant of\nautored
 ucibility\, where we require the oracle Turing machine to run in\npolynomi
 al time.\n\nThe question of whether complete sets for various classes are\
 npolynomial-time autoreducible has been studied extensively. In some cases
 \,\nit turns out that resolving autoreducibility can result in interesting
 \ncomplexity class separations. One question that remains open is whether\
 nall Turing complete sets for NEXP are Turing autoreducible. An important\
 nseparation may result when solving the autoreducibility for NEXP\; if the
 re\nis one Turing complete set of NEXP that is not Turing autoreducible\,\
 nthen EXP is different from NEXP. We do not know whether proving all\nTuri
 ng complete sets of NEXP are Turing autoreducible yields any\nseparation r
 esults.\n\nBuhrman et al. showed that all\n${le_{mathit{2mbox{-}tt}}^{math
 it{p}}}$-complete\nsets for EXP are\n${le_{mathit{2mbox{-}tt}}^{mathit{p}}
 }$-autoreducible.\nThis proof technique exploits the fact that EXP is clos
 ed under\nexponential-time reductions that only ask one query that is smal
 ler in\nlength. Difficulties arise when we want to prove that the above re
 sult\nholds for NEXP\, because we do not know whether this property still 
 holds\nfor NEXP. To resolve that difficulty\, we use a nondeterministic te
 chnique\nthat applies to NEXP and obtain the similar result for NEXP\; tha
 t is\, all\n${le_{mathit{2mbox{-}tt}}^{mathit{p}}}$-complete\nsets for NEX
 P are\n${le_{mathit{2mbox{-}tt}}^{mathit{p}}}$-autoreducible.\nUsing simil
 ar techniques\, we can also show that every disjunctive\nand conjunctive t
 ruth-table complete set for NEXP is disjunctive and\nconjunctive truth-tab
 le autoreducible respectively. In addition to those\npositive results\, ne
 gative ones are also given. Using different notions\nof reductions\, we ca
 n show that there is a complete set for NEXP that\nis not autoreducible. F
 inally\, in the relativized world\, there is a\n${le_{mathit{2mbox{-}T}}^{
 mathit{p}}}$-complete set for\nNEXP that is not Turing autoreducible.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR