tag:blogger.com,1999:blog-3722233.post3346846996004666943..comments2021-06-24T09:55:26.819-05:00Comments on Computational Complexity: IdiotLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger23125tag:blogger.com,1999:blog-3722233.post-71003370439516917732007-05-02T12:09:00.000-05:002007-05-02T12:09:00.000-05:00Thanks dudes,If i got it correctly, then by the ti...Thanks dudes,<BR/><BR/><BR/>If i got it correctly, then by the time-hierarchy thm. it is guaranteed that there are <BR/>problem in P which requires say n^1000 time to solve, yet the proof is not constructive,<BR/>and there are no 'natural' problems for which we know that they take more then say n^2?<BR/>(when any algorithm allowed, not on a restricted circuit model).<BR/><BR/>What then is the best gap known between finding a solution and verifying it? <BR/>can one prove that there exist a problem for which finding the solution takes n^1000, <BR/>but verifying it takes n^2 or something like this?<BR/><BR/>Complexity laymenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39492464185630113162007-05-01T23:43:00.000-05:002007-05-01T23:43:00.000-05:00Complexity layman wrote:2. What is the best lower ...Complexity layman wrote:<BR/><BR/>2. What is the best lower bound known for an algorithm which solves an NP-complete problem?<BR/>I know there are good lower bounds for restricted models of computations (e.g. all kinds of circuits),<BR/>but what is the state of the art for algorithms? Is it n^2? some other power of n? <BR/><BR/><BR/>To add to what responder 20 wrote about the Time Hierarchy theorem, one can also construct a language L that is in NTIME[n^k] but not in NTIME[o(n^k)] (for multitape TMs we may need to fuzz this up by a logn factor or so). Then L+SAT (i.e., {0x : x \in L} U {1x: x \in SAT} is NP-complete and has a lower bound of time n^k for NTIME. hence also for DTIME.<BR/><BR/>But most of the classic NP-complete problems actually live in nondeterministic linear time (NLIN). Yet of those, only barely-superlinear lower bounds (coming from NLIN != DLIN for multitape TMs) are known, and only for a few such problems! <BR/><BR/>This and other concrete lower bound issues are treated in my <A HREF="http://www.cse.buffalo.edu/~regan/papers/pdf/linsurvey.pdf" REL="nofollow">Oct. 1993 SIGACT News survey article</A>, which is still up to date to a depressing degree :-0!KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19265418816472457572007-05-01T09:14:00.000-05:002007-05-01T09:14:00.000-05:00Regarding point #2: There are lots of results tha...Regarding point #2: There are lots of results that prove superpolynomial lower bounds for particular approaches to solving NP-complete problems. <BR/><BR/>For example, there is a subfield called "proof complexity" which shows that for specific proof systems, proofs that certain CNFs are unsatisfiable require superpolynomial size. While this does not clearly say anything about all possible satisfiability algorithms, it does give lower bounds on many approaches that are used in practice.<BR/><BR/>See the survey "Lengths of Propositional Proofs" by Alasdair Urquhart.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90000126366519385872007-05-01T06:49:00.000-05:002007-05-01T06:49:00.000-05:00In reverse order:3. The time hierarchy theorem (wh...In reverse order:<BR/><BR/>3. The time hierarchy theorem (which should be in any book on complexity or computability theory) tells us in particular that for every k there are problems solvable in time n^k but not time n^{k-1}. This is one of the few things we know without any assumptions!<BR/><BR/>2. I don't know the "best" answer to this question, though my favorite is the proof that clique require super-polynomial size *monotone* circuits. You need to look at individual problems here for the reasons discussed below.<BR/><BR/>1. I think you have to ask on a problem-by-problem basis. To see this, note that by padding an NP-complete problem with sufficiently many 0s you can always construct an NP-complete problem solvable in time n^\epsilon for any positive \epsilon.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27944577888651516082007-05-01T06:29:00.000-05:002007-05-01T06:29:00.000-05:00Complexity for idiots:As an outsider with some int...Complexity for idiots:<BR/><BR/>As an outsider with some interest in complexity, i've got a few very basic/idiotic questions - <BR/>couldn't find answers in standard textbooks/papers (though didn't try too hard) :<BR/><BR/><BR/>1. What is the best known running time for an algorithm which solves an NP-complete problem?<BR/>I guess something like 'enumerate all possibilities' give you ~2^n. Is it possible to do better?<BR/>e.g. \alpha^n for \alpha<2 ? or 2^{n/2} or even 2^{\sqrt(n)} ?<BR/><BR/>2. What is the best lower bound known for an algorithm which solves an NP-complete problem?<BR/>I know there are good lower bounds for restricted models of computations (e.g. all kinds of circuits),<BR/>but what is the state of the art for algorithms? Is it n^2? some other power of n? <BR/><BR/>3. Could the following situation be true? NP=P, but for every natural number k, <BR/>there exists a problem such that the running time of any algorithm solving it is at least O(n^k) ?<BR/>Or, alternatively, does NP=P imply that there is some universal k (e.g. k=17) such that for all problems in P <BR/>we've got an algorithm with running time O(n^k)?<BR/><BR/><BR/>My hunch is that other mathematicians/scientists may have more questions which are at this level (I feel no longer <BR/>embarrassed about my ignorance after talking to a FEW physicists still thinking that NP is 'Not Polynomial')<BR/>could this blog be a good place to discuss them? (If there's some other place suitable for this i'd be happy to know) <BR/><BR/><BR/>Thanx,<BR/>Complexity laymenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49415080755281926062007-04-29T13:47:00.000-05:002007-04-29T13:47:00.000-05:00Perhaps you still are an idiot.Just want to mentio...<I>Perhaps you still are an idiot.</I><BR/><BR/>Just want to mention that such stupid comments are stupid!!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63932177115833618112007-04-28T19:07:00.000-05:002007-04-28T19:07:00.000-05:00We, the readers of Computational Complexity, are e...We, the readers of Computational Complexity, are eagerly awaiting the next Podcast. When is it going to happen?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84167301570893277932007-04-28T19:05:00.000-05:002007-04-28T19:05:00.000-05:00> I miss being an idiot.Perhaps you still are an i...> <EM>I miss being an idiot.</EM><BR/><BR/>Perhaps you still <B>are</B> an idiot.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13964085626494238132007-04-28T15:37:00.000-05:002007-04-28T15:37:00.000-05:00The problem is that computers used to not work ver...The problem is that computers used to not work very well, so no one was surprised when they failed. It usually wasn't that hard to get them to kinda work again, so we felt stupid when we saw how easy it was. Now we tend to think that computers actually work, and are surprised when they don't. And when they don't, it's not so easy to get them working again.<BR/><BR/>-- from one who can attest that Bill actually wasn't an idiot in the old days :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44713578567309533922007-04-28T04:37:00.000-05:002007-04-28T04:37:00.000-05:00thank you very very nıce thankyou very very much.....thank you very very nıce thankyou very very much...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73226552088883065072007-04-27T12:31:00.000-05:002007-04-27T12:31:00.000-05:00Ask all the knowing google - and it provides with ...Ask all the knowing google - and it provides with an answer and does not call you names!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45613033348601614752007-04-27T12:03:00.000-05:002007-04-27T12:03:00.000-05:00Which is to say, the "average person's intellect" ...<I>Which is to say, the "average person's intellect" is pretty much exactly like the intellect of the average theoretician!</I><BR/><BR/>Not if you substitute "average <I>successful</I> theoretician". <BR/><BR/>Just what is the average IQ of people who publish papers in STOC/FOCS?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81277450246510300942007-04-27T11:05:00.000-05:002007-04-27T11:05:00.000-05:00Anonymous says: Computers are probably better at p...Anonymous says: <I>Computers are probably better at proofs than the vast majority of people could ever be. It is easy for theoreticians to forget what the intellect of the average person is like.</I><BR/><BR/>Which is to say, the "average person's intellect" is pretty much exactly like the intellect of the average theoretician!<BR/><BR/>The book <I>A=B</I> (available on-line) has a wonderful introduction by Donald Knuth on this topic. <BR/><BR/>The book <I>A=B</I> itself has many examples of results that would be thought wonderful ... if they had been derived by a human theoretician!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14559561747887366812007-04-27T09:02:00.000-05:002007-04-27T09:02:00.000-05:00Sure. But this is not the case here.Computers are ...<I>Sure. But this is not the case here.</I><BR/><BR/>Computers are probably better at proofs than the vast majority of people could ever be.<BR/><BR/>It is easy for theoreticians to forget what the intellect of the average person is like.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15051146879278834862007-04-27T06:02:00.000-05:002007-04-27T06:02:00.000-05:00Anon 7: is that true? It sure isn't clear from the...Anon 7: is that true? It sure isn't clear from the FRCC webpage...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2430323541736351862007-04-27T04:39:00.000-05:002007-04-27T04:39:00.000-05:00A dropoff in some abilities is not so bad provided...<I>A dropoff in some abilities is not so bad provided that there is a substantial gain along some other dimensions and that gain is useful in some way.<BR/><BR/>Additionally, a dropoff for some abilities may not be so bad provided that computers can be used as a replacement for those abilities.</I><BR/><BR/><BR/>Sure. But this is not the case here.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86159823122773686252007-04-27T01:59:00.000-05:002007-04-27T01:59:00.000-05:00did anyone already register for FCRC? it's quite c...did anyone already register for FCRC? it's quite costly. <BR/><BR/>As Lance claimed you could attend any session on any day you are registered, the best strategy seems to be to register only for EC, which would get you completely covered also for STOC and COMPLEXITY. <BR/><BR/>A remarkable 3 for 1 deal!!!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40594581939441766182007-04-27T00:59:00.000-05:002007-04-27T00:59:00.000-05:00Thag here. Thag's day, everyone live cave, make f...Thag here. Thag's day, everyone live cave, make fire good. These days, kid say "Twigs wet. Hard make fire. Kid go house, play X-Box." Make Thag sad.<BR/><BR/>Thag go now, try thump stupid kid.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25984730081238042432007-04-26T22:48:00.000-05:002007-04-26T22:48:00.000-05:00I observe and theorize that today's teens and coll...<I>I observe and theorize that today's teens and college (and now grad-school) population have higher "Gestalt", graphical, and navigational abilities, but on pain of a notable dropoff in "linear" reasoning ability (proofs, discrete math...). They do "E-Search not Research", and tend to read in tree form, not in book form. Darkly I wonder if this effect of growing up with computers and the Net may be more pernicious than TV was for "Why can't Johnny read?", because it is masked by other enhanced abilities and affects rigor and reasoning style directly.</I><BR/><BR/>A dropoff in some abilities is not so bad provided that there is a substantial gain along some other dimensions and that gain is useful in some way.<BR/><BR/>Additionally, a dropoff for some abilities may not be so bad provided that computers can be used as a replacement for those abilities.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19781228044665258832007-04-26T21:58:00.000-05:002007-04-26T21:58:00.000-05:00The gap is much larger for kids in absolute terms,...The gap is much larger for kids in absolute terms, but the immersion in computers enables them to navigate at least the software side with ease.<BR/><BR/>I have trouble acquiring the coordination to make video-game characters do much more than jump over obstacles and occasionally whirl and punch-or-fire. Whereas I've seen my kids (9 and 12) pick up the next video game quickly given their experience with previous ones. There also good at getting around Windows and MacOS X and MS Word/art-addons in general.<BR/><BR/>I observe and theorize that today's teens and college (and now grad-school) population have higher "Gestalt", graphical, and navigational abilities, but on pain of a notable dropoff in "linear" reasoning ability (proofs, discrete math...). They do "E-Search not Research", and tend to read in tree form, not in book form. Darkly I wonder if this effect of growing up with computers and the Net may be more pernicious than TV was for "Why can't Johnny read?", because it is masked by other enhanced abilities and affects rigor and reasoning style directly.KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22274040135243155552007-04-26T18:50:00.000-05:002007-04-26T18:50:00.000-05:00For the "Ramsey-theory idiots" out there, the tech...For the "Ramsey-theory idiots" out there, the technical translation of VDW(4,2) is: "I don't know exactly how much more complicated computers have gotten, but it's a whole hell of a lot!" :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20061452883977263522007-04-26T17:50:00.000-05:002007-04-26T17:50:00.000-05:00See also Communicating Sequential Processes, Const...See also Communicating Sequential Processes, Constraint Satisfaction Problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63221939547540119862007-04-26T16:30:00.000-05:002007-04-26T16:30:00.000-05:00I grev up more or less at the same rate as the per...I grev up more or less at the same rate as the personal computer gre up, I played with bizzare incompatible things in the early eighties and you had a good chance of understanding what the bits and pieces of your computer were.<BR/><BR/>To children born today the gap is much larger, and computers can do much much more than black and white pong. For most people computers are moving into the realm of Clarke's<BR/>"Any sufficiently advanced technology is indistinguishable from magic"Anonymousnoreply@blogger.com