DanielFilan comments on Alignment proposals and complexity classes

DanielFilan 17 Jul 2020 1:00 UTC
LW: 8 AF: 4
AF
It doesn’t talk about using M as an oracle, but otherwise I don’t see how the proofs pan out: for instance, how else is

Given $p$ , return $M (p : s_{0} : [] : x_{0} : [])$ where $s_{0} \in S_{p}$ is the initial state of $T_{p}$ , $x_{0}$ is the empty tape symbol, and $:$ is string concatenation.

supposed to only take polynomial time?
- adamShimi 17 Jul 2020 21:04 UTC
  LW: 3 AF: 2
  AF Parent
  You’re right, after rereading the proofs and talking with Evan, the only way for H to be polynomial time is to get oracle access to M. Which is slightly unintuitive, but makes sense because the part of the computation that depends on H and not on M is indeed polynomial time.