tag:blogger.com,1999:blog-3722233.post200039297..comments2019-08-24T09:29:36.337-04:00Comments on Computational Complexity: Foundations of Complexity Lesson 16: Ladner's TheoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-49744182157495163682015-11-10T10:45:20.577-05:002015-11-10T10:45:20.577-05:00Re Muchnik Friedberg. Somewhat oddly, the proof of...Re Muchnik Friedberg. Somewhat oddly, the proof of Ladner's theorem is actually easier than Muchnik Friedberg because no prioirities are needed. Maybe that's because for small inputs you can solve SAT in polytime but for no inputs however small can one in general solve the halting problem (which plays the role of SAT in Muchnik Friedberg). Usually, complexity is more complicated than computabilitiy, but in this case it seems to be the other way...Martin Hofmannhttps://www.blogger.com/profile/00972885786307321314noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41473062997800221452015-11-10T10:31:45.232-05:002015-11-10T10:31:45.232-05:00Yes, after looking up Arora and Barak, I found the...Yes, after looking up Arora and Barak, I found the same fix. Thanks very much, this saves me from having to prepare a completely new proof for my class :-)Martin Hofmannhttps://www.blogger.com/profile/00972885786307321314noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74801741548438045452015-11-10T08:43:32.588-05:002015-11-10T08:43:32.588-05:00Thanks for your comments on the paper. We can fix ...Thanks for your comments on the paper. We can fix the proof by taking say |x|<=log log n. I'll try to update the paper when I get a chance. Basically the same proof works for polytime Turing reductions as well even for NP. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90551725767898596172015-11-10T07:55:48.028-05:002015-11-10T07:55:48.028-05:00I wonder if there is a problem with the "firs...I wonder if there is a problem with the "first proof": In case 2 on page 2 we must check whether f_i(x) is in SAT or not. This takes time O(2^(|x|^i)) = O(2^(log n)^i) and even for i=2 this is not polynomial in n. Am I wrong? <br />Martin Hofmannhttps://www.blogger.com/profile/00972885786307321314noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2107501233163012942015-11-10T05:22:23.369-05:002015-11-10T05:22:23.369-05:00replace PSPACE with Delta_2 or something...replace PSPACE with Delta_2 or something...Martin Hofmannhttps://www.blogger.com/profile/00972885786307321314noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53042464978538768182015-11-10T05:19:04.507-05:002015-11-10T05:19:04.507-05:00Another comment: Muchnik Friedberg is about Turing...Another comment: Muchnik Friedberg is about Turing reductions. So maybe the analogue would rather be: If P =/= PSPACE then there exist languages L1,L2:PSPACE such that L1 not in P^L2 and L2 not in P^L1.Does that hold?Martin Hofmannhttps://www.blogger.com/profile/00972885786307321314noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68542925106766620242015-11-10T05:12:16.522-05:002015-11-10T05:12:16.522-05:00Dear Lance, thank you for the writeup which I foun...Dear Lance, thank you for the writeup which I found the most suitable one I found. A minor remark: the f(n) at the end of the fourth last line of the first proof should be n, right? Martin (Hofmann)Martin Hofmannhttps://www.blogger.com/profile/00972885786307321314noreply@blogger.com