AlexMennen comments on Tiling Agents for Self-Modifying AI (OPFAI #2) - Less Wrong

55 Post author: Eliezer_Yudkowsky 06 June 2013 08:24PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (260)

You are viewing a single comment's thread. Show more comments above.

Comment author: AlexMennen 02 July 2013 01:17:40AM 0 points [-]

in both cases, almost the entire polynomial hierarchy will collapse

Why?

Comment author: JoshuaZ 02 July 2013 01:36:48AM *  0 points [-]

in both cases, almost the entire polynomial hierarchy will collapse

Why?

Well, in the easy case of ZPP, ZPP is contained in co-NP, so if NP is contained in ZPP then NP is contained in co-NP, in which case the hierarchy must collapse to the first level.

In the case of BPP, the details are slightly more subtle and requires deeper results. If BPP contains NP, then Adelman's theorem says that then the entire polynomial hierarchy is contained in BPP. Since BPP is itself contained at finite level of the of the hierarchy, this forces collapse to at least that level.