tag:blogger.com,1999:blog-3722233.comments2019-03-24T22:24:24.608-04:00Computational ComplexityLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger22349125tag:blogger.com,1999:blog-3722233.post-48783865464678499022019-03-24T22:24:24.608-04:002019-03-24T22:24:24.608-04:00I have made the correction and also pondered if Go...I have made the correction and also pondered if Goodwin's law holds in Nazi chatrooms.<br />(If the comments on this post go off topic I will only have myself to blame.)GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39568110045601983272019-03-24T21:17:20.901-04:002019-03-24T21:17:20.901-04:00Wikipedia says that's "Goodhart's law...Wikipedia says that's "Goodhart's law". I guess "Goodwin's Law" is Goodhart's law + Godwin's law? "As a measure becomes a target, the probability of a comparison with Nazis approaches 1"?<br /><br />(Sorry. Also *is -> it in the italicized text.)Aaron Rotenberghttps://www.blogger.com/profile/04025704694247832990noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79603855804180955482019-03-24T17:58:29.576-04:002019-03-24T17:58:29.576-04:00I wonder what is the attitude in the US towards &q...I wonder what is the attitude in the US towards "Option 13": Go to a school outside the continent, where it is more about proficiency in the studied discipline.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65705717686081966792019-03-24T04:46:07.981-04:002019-03-24T04:46:07.981-04:00I read the book ("Printed as BoD"), it m...I read the book ("Printed as BoD"), it makes a light and inspiring reading as Ken Regan already observed. For ex-researchers some rusty math- and tcs-reminiscences are revived. Teachers will find a wealth of material to be used in class and puzzlers can update their stock of problems.<br />For the second edition two corrections:<br />Lemma 13.3 has b_n = 0 mod a, but according to Definition 13.4. it should be b_n-1.<br />Lemma 21.1 (1) does probably need that a and b are mutually prime. A counterexample is (2) as sigma(2) = 3 and Sigma (4) = 7 != 9.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16937191297032431782019-03-21T03:52:52.810-04:002019-03-21T03:52:52.810-04:006) Wrong. Baar Baar Dekho, a British kid of Pakist...6) Wrong. Baar Baar Dekho, a British kid of Pakistani Muslim background born in 2005 growing up in the London area found a P=NP algorithm in 2031/32 making an enormous fortune for himself as the West collapsed.Or EinSofhttps://www.blogger.com/profile/03281901712454837586noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6012162861204697832019-03-19T20:32:09.940-04:002019-03-19T20:32:09.940-04:00In response to William Hoza's answer:
Even if...In response to William Hoza's answer:<br /><br />Even if we did find an algorithm that solves SAT in polynomial time, I do not know of any guarantee that we can prove the algorithm's correctness in every case (even if it is correct in every case).<br /><br />His response, of course, suggests that some finitely-expressible tautologies do not have finite proofs. This goes against my feelings that math is never arbitrary or without reason, since a proof is no more than an explanation of why the tautology is true.<br /><br />If it weren’t for the possibility of being unable to prove the supposed algorithm’s correctness, the following logic would have applied:<br /><br />Claim:<br />Defining any finitely-expressible object x, it is impossible to prove that there is no proof of whether or not x exists.<br /><br />Not quite a proof:<br />*Suppose a proof Q exists, showing that it is impossible to prove whether or not x exists.<br /><br />*We can now conclude that x does not exist because if it did, we could give x as a proof that it does, which would contradict Q. However, this still contradicts Q: we have proven that it does not exist.<br /><br />*On second thought, x must exist, otherwise we get the above contradiction. But that still contradicts Q: we have proven that x does exist.<br /><br />*Either way, you can never proof that there is no proof of whether or not x exists, knowing there are only two possibilities: it exists or it does not. We have exhausted both.<br /><br />Except, simply showing x does not prove x exists, interestingly. That is, showing an object with some property does not prove it has that property.Jake Thomashttps://www.blogger.com/profile/07615136588086240691noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78356044310992646712019-03-18T22:31:19.224-04:002019-03-18T22:31:19.224-04:00This is a fine point of view. There are indeed som...This is a fine point of view. There are indeed some cases where we can show a poly time algorithm exists but cannot find one. Abstractly we can use the knowledge that one exists to find one that involves running lots of Turing Machines, but to REALLY have one may be difficult. For example, for any g there is an O(n^3) algorithm to test of a graph has genus g since genus-g is closed under minors and hence has a finite obstruction set. But the proof that it has a finite obs set is nonconstructive (I do not know if this particular case they know more constrivelty).<br /><br />So indeed, we may one day find that P=NP but the algorithm is non-constructive. GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68064987027223878422019-03-18T09:16:03.552-04:002019-03-18T09:16:03.552-04:00Clancy doesn't claim that they've simulate...Clancy doesn't claim that they've simulated a quantum computer with the Super-Connector. He says that programming the computer was prohibitively inefficient until they found a way to apply quantum theory.drng987https://www.blogger.com/profile/13583017726289923564noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23039653542102657342019-03-18T04:32:36.759-04:002019-03-18T04:32:36.759-04:00nice. I looked through it. My question to Bill and...nice. I looked through it. My question to Bill and Lance,<br />how should I interpret this the following opinion voiced in the survey:<br /><br />"I can't wait for people to realize that P=?NP is only a question about the existence of a poly-nomial time algorithm, not about the knowledge of one. We already know, for example, that there exists a polynomial time algorithm to decide membership in any given minor-closed graph family; but we don’t know how to really decide it, except for a few actual families"<br /><br />And yes, that Don Knuth voicing it.Enoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55333478764055231752019-03-15T06:24:33.443-04:002019-03-15T06:24:33.443-04:00https://aviation-safety.net/graphics/infographics/...https://aviation-safety.net/graphics/infographics/Fatal-Accidents-Per-Mln-Flights-1977-2017.jpg<br /><br />... I don't know about you, but I don’t want Donald Trump to be my president ... :-DMarzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11013169758789237822019-03-14T20:55:39.802-04:002019-03-14T20:55:39.802-04:00It seems that the hardware change was put in to im...It seems that the hardware change was put in to improve fuel efficiency so "re-designing the hardware" would defeat the whole purpose. <br /><br />One thing I have no clue about is whether the software is necessary for general safety or just in order to make the plane "fly like a 737" so that pilots don't need separate certification to fly it. Paul Beamehttp://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63553813215612312362019-03-14T10:55:35.577-04:002019-03-14T10:55:35.577-04:00From what I (as a layman) understand, the new plan...From what I (as a layman) understand, the new plane had oversized engines stuck in an awkward place, and this was compensated for by the software. In this sense "simpler" (redesigning the hardware to not require extra software) would have been better (albeit not cheaper).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74838428014401250952019-03-12T17:44:45.894-04:002019-03-12T17:44:45.894-04:00I add my comment 8 years after the original post -...I add my comment 8 years after the original post - but the theme is still current.<br />I tested a bit TeXmacs (http://www.texmacs.org/tmweb/home/welcome.en.html) and I think it goes in the right direction: it is at the same time structured and WYSIWYG. In the experience I did in the last few months, there are a few things that do not work yet well: sometimes it crashes, it happened to me when executing a small macro; and it does not have an organized place for the exchange of style files and macros at the moment. And by the way I tried it for small documents only.<br />But I think the idea is right and the implementation is good. Macros with parameters give immediate WYSIWYG output to screen (perhaps there a bit of flexibility would help, in the sense of switching between code and output, I have not been able to figure out whether it is possible).<br />By the way the screenshots on the homepage are a bit outdated, the most recent versions look more modern!<br />The pdf output is excellent, and one can export almost perfect LaTeX (I tried it a bit, I had to make a few corrections) and can import very reasonably (a few corrections were necessary in the tests I did).JTShttps://www.blogger.com/profile/16381322139959132720noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21124579182857164872019-03-12T09:13:16.564-04:002019-03-12T09:13:16.564-04:00http://www.fields.utoronto.ca/activities/18-19/NP5...http://www.fields.utoronto.ca/activities/18-19/NP50Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34488551365119310082019-03-10T19:16:03.613-04:002019-03-10T19:16:03.613-04:00At 12:44-13:20 in the fireside chat at Simons, we ...At 12:44-13:20 in the fireside chat at Simons, we hear Dick say:<br />Parallel computation was quite important in the 80s, I think there was a lot of work on parallel computation ... and that seems to have faded, but I expect that it will be making a comeback, since it is really so terribly relevant.<br />Samir: multicore processing is still a big topic, within architecture<br />Dick: that is right, that is true, but it hasn't been accompanied by a corresponding push on the theoretical side, seems to be that is overdue<br /><br />A Survey of Parallel Algorithms for Shared-Memory Machines (70 pages)<br />https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5865.html<br />https://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-408.pdf<br />by Richard M. Karp and Vijaya Ramachandran – March 1988Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66172971126221901422019-03-05T23:52:16.041-05:002019-03-05T23:52:16.041-05:00Have you seen Michael Nielsen's post about the...Have you seen Michael Nielsen's post about the results of ths interaction betweee two pricing algorithms? https://web.archive.org/web/20111206064435/http://www.michaeleisen.org/blog/?p=358Diegohttps://www.blogger.com/profile/09627662189360325919noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46642326704999170712019-03-05T21:12:01.907-05:002019-03-05T21:12:01.907-05:00I once saw (a few years ago, WAY after video tapes...I once saw (a few years ago, WAY after video tapes were a thing) a copy of the video tape for the movie Network on sale for about $1000. I've also seen obscure books, not colletables, for $1000. Those I thought were money laundering. but my book for about 20 bucks over list? Seems like an inefficient way to money launder. Unless bots?GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69119132161296798882019-03-05T20:57:24.713-05:002019-03-05T20:57:24.713-05:00I think that a variation on 4 is a likely explanat...I think that a variation on 4 is a likely explanation: The seller sends it as a gift from Amazon to the buyer and pockets the difference. (My wife saw this recently on an item sold through eBay. In that case, the eBay description didn't quite match the item delivered by Amazon so she was able to get the refund on eBay and then return it to Amazon.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58532190347282683462019-03-05T05:50:20.138-05:002019-03-05T05:50:20.138-05:00Good idea. Could also be a scheme to improve ratin...Good idea. Could also be a scheme to improve ratings, in addition to laundering money.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34275520074658182602019-03-05T03:41:58.572-05:002019-03-05T03:41:58.572-05:00Different selling shops might work with different ...Different selling shops might work with different taxes/customs? On amazon.de you cost by default 39.50/74.30 euros, which is quite more. Also, it doesn't sell any used copies, so whoever stole your book and didn't like it, lives in the US!<br /><br />ps. Typo: "found our" -> "found out"domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25051071747332920042019-03-04T22:49:48.641-05:002019-03-04T22:49:48.641-05:00This is a complex in-public money laundering schem...This is a complex in-public money laundering scheme. By pricing the copies above what the Amazon prices are, they greatly decrease the chances of some random person actually ordering the book from them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49488760745754790072019-03-02T08:39:36.033-05:002019-03-02T08:39:36.033-05:00... If P = NP we can solve AI! ...
That argument ...... If P = NP we can solve AI! ...<br /><br />That argument holds if you use AI for very "formal" applications. Even if you have an efficient NP algorithm for NP, to handle "natural" problems like speech recognition, language translation, OCR, ... you would end up doing things similar to what AI people do now.Majdodinhttps://www.blogger.com/profile/06638299762577890471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33333874150352161762019-03-02T08:30:02.388-05:002019-03-02T08:30:02.388-05:00... nearly all the known problems we know that sit...... nearly all the known problems we know that sit in polynomial time have practical efficient solutions ...<br /><br />That is arguable: For example, consider the (rightly) celebrated log-space algorithm of Omer Reingold for st-connectivity in undirected graphs. It has a polynomial runtime, O(n^c), but c >> 10^9.<br />see https://cstheory.stackexchange.com/questions/1063/time-complexity-analysis-for-reingolds-ust-conn-algorithmMajdodinhttps://www.blogger.com/profile/06638299762577890471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66166346432702382792019-03-02T08:02:37.905-05:002019-03-02T08:02:37.905-05:00What if AI can self-educate itself to solve TCS pr...What if AI can self-educate itself to solve TCS problems better than any theorist, in the same way that AlphaZero self-trained itselt to beat all chess masters and other chess programs?Majdodinhttps://www.blogger.com/profile/06638299762577890471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20637424868614930832019-03-01T11:00:07.059-05:002019-03-01T11:00:07.059-05:00Are theorists (specifically when wearing the compu...Are theorists (specifically when wearing the computational complexity hat) ever driven by real world applications? Algorithm theorists perhaps aspire for their algorithms to be used some day. <br /><br />I am not aware of any ideas and methods that hard core application oriented folks (especially with machine learning flavor) could bring to hard core theorists (and vice versa); perhaps I am being pessimistic. <br /><br />Machine learning folks are having their field day in the sunshine and are truly relishing it (perhaps also rubbing it in into others in different fields). <br /><br />I don't believe theorists ever had short term horizons for their science; their endeavors therefore cannot be quantified with a tangible easy-to-define (and verify) metric. The society has valued their work in the past and one hopes will continue to do so in the future despite the comings and goings of new technologies.space2001noreply@blogger.com