tag:blogger.com,1999:blog-3722233.post6856990406290535196..comments2023-03-27T17:26:46.668-05:00Comments on Computational Complexity: FOCS V- Report from Prog Comm.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-69041711460828400662008-08-27T12:26:00.000-05:002008-08-27T12:26:00.000-05:00My recent research finds that we can build a Voron...My recent research finds that we can build a Voronoi diagram with the d-dimension in nlogn.<BR/><BR/>This is really interesting! I suddenly find people only can efficiently address VD in a plane before. For d-dimension, it is N^[d/2].<BR/><BR/>Finally, I realize that the VD problem and other NP problem belong to the same group of hard problem (not exact).<BR/><BR/>I also realise that people tend to give an optimal solution by combination. But it is not an arithmetic description about solution. The combination is bad computation in the practical applications.<BR/><BR/>All techniques are only traditional. But problem should be geometrically described.<BR/><BR/>I write these here as a trace such that the final result verifies what I say in future.<BR/><BR/>JohnAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29711183441043127962008-08-26T21:36:00.000-05:002008-08-26T21:36:00.000-05:00all geometric computation can be linearithmic or l...all geometric computation can be linearithmic or loglinear.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60462125973922742572007-12-05T20:48:00.000-06:002007-12-05T20:48:00.000-06:00Sorry, a bug. It should be f(k)T^3.JohnSorry, a bug. It should be f(k)T^3.<BR/><BR/>JohnAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80841994523606560642007-12-05T17:21:00.000-06:002007-12-05T17:21:00.000-06:00P=NP is right! This is because an assigment for sa...P=NP is right! This is because an assigment for satisfication has a lot of redundancies. <BR/><BR/>For example<BR/><BR/>X + Y + Z only need X =1 or Y =1 or Z=1, we do not need X=1 and Y =1...<BR/>Therefore, for reasoning of proposational rule can be simplified, e.g, for distribution for disjuctive rule.<BR/><BR/>The main error of the previous method is to converge to a solution from a huge of hyperspace.<BR/><BR/>Any combination with backtrack or backjump is a worse computation. A tree search is essentially a combination !<BR/><BR/>The algorithmic complexity is 2^k T^3<BR/><BR/>where k is the maximum size of clause; T is the number of clauses.<BR/><BR/>So the algorithm can be polynomial but the description of problem can be exponential. However, who can understand a language with exponential description ?<BR/><BR/>The evidence can be verified from the transformation of SAT into 3SAT. The funny thing is the problem is not changed with its complexity even its description !<BR/><BR/>No matter 2SAT or 3SAT or SAT, and no matter how many variables, the description, still description!!!<BR/><BR/>Sergey's method is simple and naive. We can have a clear improvement by modifying a little proposational rules for reasoning without truth values.<BR/><BR/>The solution consist of the main two points, and is not new according to my observation.<BR/><BR/>Hope my observation and results can verify P=NP with Sergey.<BR/><BR/>JohnAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58729844476878449022007-10-24T18:46:00.000-05:002007-10-24T18:46:00.000-05:00anonymous #4 and #3 seem to imply that the paper o...anonymous #4 and #3 seem to imply that the paper on P=NP was rejected without serious review, solely based on title and authorship <BR/>If this is the case we have a serious problem with the integrity of the review system.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75173435610486218142007-10-24T15:34:00.000-05:002007-10-24T15:34:00.000-05:00It is rather striking that not a single learning t...It is rather striking that not a single learning theory paper made it to FOCS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36683282013158588742007-10-24T11:26:00.000-05:002007-10-24T11:26:00.000-05:00I do like how P=NP is its own category. Does that...I do like how P=NP is its own category. Does that mean there was a NP=P category, but no one submitted this year?<BR/><BR/>It seems *too* focused for a category; why not just have a catch-all "crackpot" category?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64744675521452111452007-10-24T09:25:00.000-05:002007-10-24T09:25:00.000-05:00This shows that the STOC/FOCS mafia is biased agai...This shows that the STOC/FOCS mafia is biased against the miscellaneous and out-of-scope communities.<BR/><BR/>It is time for a new conference!<BR/><BR/>Authors shold submit their best miscellaneous and out-of-scope papers to MISCO 2008Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74918036538171885792007-10-24T08:57:00.000-05:002007-10-24T08:57:00.000-05:00"FOCS is a complexity theory conference with near-...<I>"FOCS is a complexity theory conference with near-50 % acceptance rate where some other suckers have been fooled into submitting their non-core-complexity theory papers, thereby artificially inflating the 'quality' rating of acceptance percentage"</I><BR/><BR/>Funnily enough that was my interpretation of things before I even saw the figures.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23618823094486856512007-10-24T04:34:00.000-05:002007-10-24T04:34:00.000-05:00Oooh, first interpretation! I know, I know: "FOCS ...Oooh, first interpretation! I know, I know: "FOCS is a complexity theory conference with near-50 % acceptance rate where some other suckers have been fooled into submitting their non-core-complexity theory papers, thereby artificially inflating the 'quality' rating of acceptance percentage", right?Anonymoushttps://www.blogger.com/profile/07036608369536887423noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56981862884792316902007-10-24T00:07:00.000-05:002007-10-24T00:07:00.000-05:00Very informative. But I think you meant 66 (instea...Very informative. But I think you meant 66 (instead of 86) papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53016896801472282232007-10-23T23:07:00.000-05:002007-10-23T23:07:00.000-05:00Who submitted the P=NP paper? That Sergey Gubin gu...Who submitted the P=NP paper? That Sergey Gubin guy?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74134323759051077432007-10-23T22:16:00.000-05:002007-10-23T22:16:00.000-05:00What would it take for an NP=P paper to be reviewe...What would it take for an NP=P paper to be reviewed seriously? Is it often the case that papers are not reviewed seriously due to lack of credentials especially for famous unsolved problems?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53507182313470399852007-10-23T21:24:00.000-05:002007-10-23T21:24:00.000-05:00The paper actually gave a randomized algorithm for...The paper actually gave a randomized algorithm for an NP-complete problem. While RP=NP is still an impressive result, we were put off by the sell job (claiming the submission was about P vs. NP).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14286862019169966042007-10-23T17:15:00.000-05:002007-10-23T17:15:00.000-05:00P=NP is an important result; I'm surprised that th...P=NP is an important result; I'm surprised that the PC chose not to accept it, especially with the good job they did on everything else.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32645078678568278282007-10-23T17:03:00.000-05:002007-10-23T17:03:00.000-05:00A NP=P paper without an algorithm! Surely that's w...A NP=P paper without an algorithm! Surely that's worth celebrating in itself...Anonymousnoreply@blogger.com