tag:blogger.com,1999:blog-15145059.post1252159879883718096..comments2024-02-20T03:26:29.516-05:00Comments on predelusional: Scheme For Enlightenment Part Seventeen - C ChangeStephenhttp://www.blogger.com/profile/03934169832326108710noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-15145059.post-68206559795418175742008-02-20T11:29:00.000-05:002008-02-20T11:29:00.000-05:00Scott Aaronson has posted a draft of his article f...Scott Aaronson has posted a draft of his article from this month's Scientific American on the <A HREF="http://www.scottaaronson.com/writings/limitsqc-draft.pdf" REL="nofollow">limitations of quantum computers</A> (PDF). With a nice graph, he outlines classes of problems - P, BQP, NP, NP-Complete, and PSPACE. These are in order of difficulty. Map coloring is listed as NP-Complete, along with Traveling Salesman and Theorem-Proving. But i used map coloring as an example of an easy problem. I'd no idea it is considered NP-Complete. And, my C version colors the continental US in 20 milliseconds on a desktop - too small to be a really reliable timing. If this problem is m^n, where n is the number of states, then m appears to be about 1.277. If that's the case, then 100 states should require more than an hour. That would be an interesting experiment, because intuition suggests that 100 states would also be more or less instant.<BR/><BR/>The <A HREF="http://en.wikipedia.org/wiki/Graph_coloring" REL="nofollow">wiki article</A> talks about the related problem of finding the Chromatic number as NP-Hard, a class not mentioned by Aaronson. I've always thought that NP-Hard is like NP-Complete, only more so. Does it fit in between NP-Complete and PSPACE? Or is NP-Hard a synonym for PSPACE?<BR/><BR/>The quantum limitations submission is very interesting for itself. Very well presented. One of the better articles from the Library of Babel.Stephenhttps://www.blogger.com/profile/03934169832326108710noreply@blogger.com