tag:blogger.com,1999:blog-3722233.post8363639202101152028..comments2019-10-21T21:47:16.813-04:00Comments on Computational Complexity: Oracle Results are Good For YouLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-85249919986031011082012-02-27T09:27:34.934-05:002012-02-27T09:27:34.934-05:00is P with an oracle to PSPACE equal to PSPACE, the...is P with an oracle to PSPACE equal to PSPACE, the answer seems yes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91507429027540892402012-02-26T20:58:40.823-05:002012-02-26T20:58:40.823-05:00is P^PSPACE = PSPACE?is P^PSPACE = PSPACE?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89986053545273427102009-05-27T15:06:10.344-04:002009-05-27T15:06:10.344-04:00Another example: the PPST'83 result
NTIME[n] != ...Another example: the PPST'83 result <br /><br />NTIME[n] != DTIME[n] <br /><br />does not relativize. One constructs an oracle A whereby x is in A if and only if x is a yes-instance for the bounded halting problem on nondeterministic machines with oracle A. See <br /><br />http://pages.cs.wisc.edu/~dieter/Courses/2007s-CS810/Scribes/PS/lecture04.psryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45683604205128664502009-05-27T08:38:41.551-04:002009-05-27T08:38:41.551-04:00There do exist results that do not relativize, and...There <EM>do</EM> exist results that do not relativize, and do not use interactive proofs. (I was surprised no one else posted this.) How about the result that Time(f) \subset Space(f/log f)? Someone else mentioned circuit lower bounds. For other examples see <A HREF="http://www.csee.umbc.edu/~chang/papers/revisionist/rev-book.pdf" REL="nofollow">here</A>.<br /><br />It's the same in cryptography: people claim (or used to claim) that black-box separations rule out "known techniques" but there are non black-box constructions.<br /><br />As for Lipton's post, I think his main point was that relativization is not useful because it is hard to tell whether a proof technique relativizes or not.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66195403255925696062009-05-27T03:13:39.618-04:002009-05-27T03:13:39.618-04:00Thank you, Lance.Thank you, Lance.Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90014223974687671222009-05-27T01:45:37.550-04:002009-05-27T01:45:37.550-04:00Anon 3.45: If P=NP, the entire polynomial hierarch...Anon 3.45: If P=NP, the entire polynomial hierarchy collapses to P. But this just tells us that a constant number of alternations is no better than no alternations at all. PSPACE involves _polynomially_ many alternations (in particular, the number of alternations depends on the input length), and it is not at all clear if these alternations can be eliminated.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41789792436057186552009-05-26T18:09:35.946-04:002009-05-26T18:09:35.946-04:00There is a better phrase that both of you might ev...There is a better phrase that both of you might even agree on: <br /><br />"I am frustrated by oracle results."Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8506914261550869302009-05-26T16:45:07.252-04:002009-05-26T16:45:07.252-04:00"Chandra, Kozen and Stockmeyer characterized PSPAC..."Chandra, Kozen and Stockmeyer characterized PSPACE by alternating polynomial time and one could possibly use the P=NP assumption to eliminate those alternations one at a time."<br /><br />There are only two alternations because the polynomial hierarchy collapses to the second level if P=NP. Or am I wrong?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51021505224244691812009-05-26T16:19:03.312-04:002009-05-26T16:19:03.312-04:00I guess should have said, I have some issues with ...I guess should have said, I have some issues with oracle results. Sorry for "hate"...rjliptonAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52709712370089933752009-05-26T15:38:26.864-04:002009-05-26T15:38:26.864-04:00We're always eager to produce a new result
...We're always eager to produce a new result<br /> Even if an oracle we must consult<br /><br /> For though P=NP is ever open<br /> To solve it we're still hopin'<br /><br /> And though exponential search we despise<br /> We're not afraid to relativize<br /><br /> For we will never weary<br /> Of computer science theory<br /><br /> Conference on Computational Complexity Theory<br /> March 1983<br /> Santa Barbara, Californiabil gasarchnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5041749732188937622009-05-26T13:53:49.927-04:002009-05-26T13:53:49.927-04:00what circuit lower bounds ?what circuit lower bounds ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11662470149544513932009-05-26T13:34:33.215-04:002009-05-26T13:34:33.215-04:00Aren't circuit lower bounds non-relativizing?Aren't circuit lower bounds non-relativizing?Anonymousnoreply@blogger.com