tag:blogger.com,1999:blog-3722233.post112353759654811799..comments2024-11-13T15:38:29.005-06:00Comments on Computational Complexity: Favorite Theorems: Abstract ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-33611277549399059372023-02-20T18:11:13.907-06:002023-02-20T18:11:13.907-06:00try the kombayashi theoremetry the kombayashi theoremeAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62807953384503914312012-12-09T20:06:45.522-06:002012-12-09T20:06:45.522-06:00IT PLEASE.IT PLEASE.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11338291722234303272009-08-01T00:51:54.646-05:002009-08-01T00:51:54.646-05:00I owned you guys. Admit it please.
It's only...I owned you guys. Admit it please. <br /><br />It's only going to get worse.<br /><br />Computational Complexity: Favorite Theorems: Abstract ComplexityBlog Links. Bill's Home Page · Lance's Home Page ... Scott Aaronson · Sorelle Friedler · Suresh Venkatasubramanian ... That is, no algorithm for MM based on self-reduction can be (x^{1+epsilon})-optimal for all epsilon>0 ...<br />blog.computationalcomplexity.org/.../favorite-theorems-abstract-complexity.htmlM-Wavehttps://www.blogger.com/profile/13408947017986840811noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80554843812794003242009-08-01T00:48:40.419-05:002009-08-01T00:48:40.419-05:00Umm guys... have you seenmy proof;
google-coop-np...Umm guys... have you seenmy proof;<br /><br />google-coop-np&cof=<br /><br />http://www.google.com/custom?hl=en&client=google-coop-np&cof=FORID:9%3BAH:left%3BS:http://MeAmI.org/%3BCX:MeAmI%252Eorg%3BL:http://MeAmI.org/beatit.jpg%3BLH:77%3BLP:1%3BLC:%233366FF%3BVLC:%2333FF00%3BGALT:%23551A8B%3BNB:1%3B&ad=w9&cx=000961116824240632825:5n3yth9xwbo&adkw=AELymgUHHvoGruIQO3xTh2DkCtUM_Fvn_8dpar0t16wkE_c1tTY5rw6LUNXxSACzcx_Pn5yBvYz14SgC71DAxH7G09hGigaMF-cVfOqwx1fSHcVQQ_LP44Zlt2zB8uckm1MMWZ5aE2kF&rurl=http://www.meami.org/%3Fcx%3D000961116824240632825%253A5n3yth9xwbo%26cof%3DFORID%253A9%253B%2BNB%253A1%26ie%3DUTF-8%26q%3DMM%2Bscottaaronson.com%252Fblog%26google_rsg%3D__f6Bxd3SkXPIINV9tMyb6fb7mYEQ%3D&q=MM+scottaaronson.com/blog&start=10&sa=N<br /><br />http://www.google.com/custom?hl=en&client=google-coop-np&cof=FORID:9%3BAH:left%3BS:http://MeAmI.org/%3BCX:MeAmI%252Eorg%3BL:http://MeAmI.org/beatit.jpg%3BLH:77%3BLP:1%3BLC:%233366FF%3BVLC:%2333FF00%3BGALT:%23551A8B%3BNB:1%3B&ad=w9&cx=000961116824240632825:5n3<br /><br /><br />Regards,<br /><br />Martin MusatovM-Wavehttps://www.blogger.com/profile/13408947017986840811noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1170800192456354742007-02-06T16:16:00.000-06:002007-02-06T16:16:00.000-06:00The deemphasis on abstract complexity including sp...The deemphasis on abstract complexity including speedup is unfortunate. For instance, three of the five problems with a monotone-nonmonotone gap (BOOLEAN MM, PERFECT MATCHING, and Tardos' CLIQUE-LIKE problem) rely upon MATRIX MULTIPLICATION, and Coppersmith and Winograd proved that no finite set of Strassen-type identities can achieve the infimum omega of all possible exponents of MM. That is, no algorithm for MM based on self-reduction can be (x^{1+epsilon})-optimal for all epsilon>0 under Blum's definition of optimality. The same holds true in Cohn et al's group theoretic framework for MM. Of the remaining two problems with a gap, BOOLEAN CONVOLUTION is conjectured by Schnorr and Stumpf not to have an optimal algorithm, and BOOLEAN SORTING provably has an optimal algorithm, but only a tiny log n gap. Note that HAMILTON CIRCUIT has an optimal algorithm by Levin's construction, as it can be verified in linear time. Therefore, the conjecture that "no problem with an \Omega(n^k) gap has an optimal algorithm" implies P!=NP, since Alon and Boppana showed that HAMILTON CIRCUIT has exponential monotone circuit complexity. If P!=NP, then all NP-complete problems have an optimal algorithm by Levin's construction. This type of argument does not relativize (too powerful an oracle eliminates the phenomena of speedup because an exhaustive search of all identities is considered uniform) nor naturalize (the proof of the existence of a faster algorithm is nonconstructive).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123685416551163562005-08-10T09:50:00.000-05:002005-08-10T09:50:00.000-05:00I view the SPEEDUP theorem as saying thatthe attem...I view the SPEEDUP theorem as saying that<BR/>the attempt to assign to every decidable<BR/>set a complexity is impossible.<BR/>That is, there are WEIRD sets for which<BR/>we cannot intelligently assign a <BR/>complexity<BR/>(e.g., there is a set A such that if<BR/>YOU say A is in DTIME(T(n)) then I<BR/>can take take that algorithm and produce<BR/>one that shows A in DTIME(log(T(n)) ).<BR/>They are like non-measureable sets of reals<BR/>which cannot be assigned a measure.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.com