tag:blogger.com,1999:blog-3722233.post1469933486217484803..comments2024-02-25T19:09:32.131-06:00Comments on Computational Complexity: Low, Superlow, supersuperlow sets, and PaywallsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-6028098980720848302012-08-22T08:37:12.439-05:002012-08-22T08:37:12.439-05:00Hello, could you please tell, does there exist a l...Hello, could you please tell, does there exist a low set, which is not superlow? I'm sure that such a set should exist, but have never seen a direct construction.Ilnurnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13758541048280943222010-12-17T11:20:57.625-06:002010-12-17T11:20:57.625-06:00I have now INCLUDED Frank Stephan's
proof in t...I have now INCLUDED Frank Stephan's<br />proof in the exposition and also changed SUPERSUPERLOW to SUPERDUPERLOW.<br /><br />THANKS to Teutsch and Frank Stephan!<br /><br />Frank's proof is in section 4.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47393893075859548052010-12-17T09:02:17.142-06:002010-12-17T09:02:17.142-06:00Anon: Great Idea! Grad or ugrad or
HS student migh...Anon: Great Idea! Grad or ugrad or<br />HS student might work for this.<br /><br />Teutsch: Please either you or Frank post the proof.<br /><br />All: The link to Kummer's cardinality theorem proof is to a paper you have to pay for. If you go to my website, click on <br />Publications with links<br />and then search for GEMS you will<br />get a FREE ONLINE survey of bounded queries in recursion theory that will include a proof of Kummer's Cardinality Theory<br />(Theorem 3.4). This is a diff proof than Kummer had.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32780054615275198562010-12-17T08:25:07.275-06:002010-12-17T08:25:07.275-06:001. Bill, this is SUPERCOOL!! (especially Lemma 2....1. Bill, this is SUPERCOOL!! (especially Lemma 2.5.)<br /><br />2. I would vote for the name "super<i>duper</i>low." It's more idiomatic.<br /><br />3. Frank Stephan just told me another proof of this fact using <a href="http://www.jstor.org/stable/2275300" rel="nofollow">Kummer's Cardinality Theorem</a>. Using this method it is possible to even get A is weakly btt below K implies A is recursive.Teutschhttps://www.blogger.com/profile/04848264673734802964noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66924861832986678182010-12-16T20:02:17.427-06:002010-12-16T20:02:17.427-06:00do you have a grad student who could learn most of...do you have a grad student who could learn most of that other stuff and co-author a paper with you? that has the "PRO" of less new stuff for you to learn outright and the "PRO" of having you help teach a grad student how to do something useful and prepare for academiaAnonymousnoreply@blogger.com