tag:blogger.com,1999:blog-3722233.post6916380312480277430..comments2023-10-04T04:25:54.403-05:00Comments on Computational Complexity: By Any Other Name Would Be Just As HardLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-4764588008592382092010-11-07T20:28:46.361-06:002010-11-07T20:28:46.361-06:00Of course, I mean circuit-value, NOT circuit-sat. ...Of course, I mean circuit-value, NOT circuit-sat. Circuit-sat being solvable in polynomial time would quite an interesting result...Mark Reitblatthttps://www.blogger.com/profile/02844686872298320790noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23683353242444120822010-11-07T19:43:06.487-06:002010-11-07T19:43:06.487-06:00Is "hard" really an accurate way of desc...Is "hard" really an accurate way of describing complete problems for a class? Every complete problem sits somewhere in that class: circuit-sat is solvable in time bounded by a specific polynomial, say of degree d. But there are plenty of problems in P that are much "harder" than circuit-sat: problems that can't be solved faster than say 2d or 2^d or 2^2^d. And they may well not be P-complete*. So then in what sense is circuit-sat "harder" than them?<br /><br />Really, completeness is a statement about expressivity, or encodability. It says that a specific problem is sufficiently expressive to encode any problem from a comparable resource class.<br /><br />*Q: Is there any theorem known about the distribution of, say. P-complete problems? Like, is it possible for there to be a P-complete problem solvable in linear-time?Mark Reitblatthttps://www.blogger.com/profile/02844686872298320790noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13679989921314020222010-11-04T18:59:47.671-05:002010-11-04T18:59:47.671-05:00It's also interesting to know that, in additio...It's also interesting to know that, in addition to the $1 million from the Clay Institute, Knuth promises 1 live turkey for a proof that P=NP. However, a proof of P \neq NP would only qualify for the money, not the turkey.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55870583375887508942010-11-04T06:12:10.197-05:002010-11-04T06:12:10.197-05:00"practically unsolvable" would have been..."practically unsolvable" would have been a good term :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41554320578653591112010-11-04T05:20:54.846-05:002010-11-04T05:20:54.846-05:00Here is your theory cafe: http://chat.stackexchang...Here is your theory cafe: http://chat.stackexchange.com<br />;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3352829865243750812010-11-02T20:27:05.507-05:002010-11-02T20:27:05.507-05:00"Riemann Hypothesis" and "Goldbach ..."Riemann Hypothesis" and "Goldbach Conjecture" sound no more friendly to the "commoner"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29083428815330081322010-11-02T15:32:02.680-05:002010-11-02T15:32:02.680-05:00GASARCH asks: "Do other fields have problems ...GASARCH asks: <i>"Do other fields have problems (and what are their names) that drive them the way P vs NP drives us?"</i><br /><br />The clear answer is "yes," and to add spice to the question, if the problem arose in the 20th century, then it is a remarkably safe bet that John von Neumann played a role in formulating it.<br /><br />Consider the range of problems that von Neumann played a key role in conceiving/defining: optimal strategies for winning games, controlling dynamical systems, and searching sets ... JvN ... consistency and decidability of formal systems ... JvN ... computational modeling of systems and enterprises ... JvN ... quantum measurement processes ... JvN ... microscopy at atomic resolution ... JvN ... DNA as a molecular string with a finite number of letters ... JvN.<br /><br />As for the still-unanswered "Giant Question" of a whether our small-ish planet Earth can support its large-ish number of people in freedom, security, and dignity ... well ... that is the still-unsolved question that <a href="http://books.google.com/books?id=HcVS1JCH_4kC&lpg=PA33&ots=nygQNFAvbm&pg=PA33#v=onepage&q&f=false" rel="nofollow">JvN was working on</a> when he passed away (at the too-young age of 54).<br /><br />Perhaps it would be a good thing if we kept working on that last JvN problem, as subsequent history has shown us that it is going to be an exceedingly tough one.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17338586937429104682010-11-02T09:30:47.570-05:002010-11-02T09:30:47.570-05:00Giant Questions:
The Riemann hyothesis.
If solved...Giant Questions:<br /><br />The Riemann hyothesis.<br />If solved this would tell us much about<br />primes so it seems big. Though it does not<br />dominate Number Theory the way that<br />P vs NP dominates complexity.<br /><br />The Goldbach Conjecture. This is a motivating problem, probably also NOT quite what you mean.<br /><br />You ask a good question- do other fields have problems (and what are there names) that drive them the way<br />P vs NP drives us?GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17347307982981997872010-11-01T19:58:48.943-05:002010-11-01T19:58:48.943-05:00I agree that NP is a confusing name, but it is mos...I agree that NP is a confusing name, but it is mostly because "nondeterminism" is confusing and hard to explain. On the other hand, the alternative definition which is more popular these days is much more intuitive: VP, verifiable in polynomial time. We could have had two definitions NP and VP and then prove in the lectures/textbooks that VP = NP, and then use VP in place of NP from that point, and in a few years we could have droped using NP, but unfortunately Valiant has already used this one.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35370221546500418892010-11-01T17:54:22.634-05:002010-11-01T17:54:22.634-05:00Can you give some examples of "giant question...Can you give some examples of "giant questions" in other fields and their simple names?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19589550338889935872010-11-01T15:19:59.296-05:002010-11-01T15:19:59.296-05:00I agree with EERac that "nondeterministic pol...I agree with EERac that "nondeterministic polynomial" is not a good name for public consumption.<br /><br />-WarrenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86450578605048587152010-11-01T12:16:59.389-05:002010-11-01T12:16:59.389-05:00By changing the names I believe we would introduce...By changing the names I believe we would introduce more confusion.<br /><br />However, if I was able to select names then I would go for this: <br /><br />"NP-complete" belong to NP and can be thought as containing all the other problems. Thus, I would use the term<br />NP-descriptive, since they can be used to describe any problem in the class.<br /><br />For "NP-hard" I would use NP-supreme, due to the resemblance to the supremum.<br /><br />I believe the original terms are much more intuitive than my ideas!Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71645546658560751982010-11-01T09:49:14.814-05:002010-11-01T09:49:14.814-05:00The main problem with terms like "NP-hard&quo...The main problem with terms like "NP-hard" and "NP-complete" is most definitely the "NP" part. The modifiers "hard" and "complete" work quite well. They are relatively intuitive, and they can be applied to a wide range of complexity classes (as opposed to, say "herculean" or "arduous").<br /><br />Meanwhile, it's quite annoying that the best way to explain the fields most well known problem, P vs. NP, involves delicately sidestepping the "N" word. A more "PC" alternative (i.e. polynomial time checkable) would make the situation far less uncomfortable.EERachttps://www.blogger.com/profile/04630819560560231513noreply@blogger.com