tag:blogger.com,1999:blog-3722233.post1508254644128697717..comments2020-12-01T15:17:08.147-06:00Comments on Computational Complexity: How hard is this problem?- I ask this non-rhetoricallyLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger69125tag:blogger.com,1999:blog-3722233.post-2258377579589252972016-03-19T19:09:07.522-05:002016-03-19T19:09:07.522-05:00Help me with this sequences. Series 10,12,13,50,46...Help me with this sequences. Series 10,12,13,50,46Anonymoushttps://www.blogger.com/profile/07645502380453255185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24362703749165802152012-11-27T19:21:20.021-06:002012-11-27T19:21:20.021-06:00found the answer in one of the sequence website. :...found the answer in one of the sequence website. :( after 15mins of thinking.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30458452037789226252011-05-26T23:34:56.185-05:002011-05-26T23:34:56.185-05:00"What are x and y?"
Well, x and y are t..."What are x and y?"<br /><br />Well, x and y are two letters of the alphabet of course! The numeric representation in ASCii is X=120 and y=121.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61112280835949565702011-01-24T12:31:15.826-06:002011-01-24T12:31:15.826-06:00tabish- that is not the answers the maker of the p...tabish- that is not the answers the maker of the problem had in mind. The sequence is the list of all numbers that, when written in English, do not have the number e in them. <br /><br />The answer is quite large.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23022416951727780032011-01-24T12:24:45.989-06:002011-01-24T12:24:45.989-06:00x=66
y=70x=66<br />y=70Anonymoushttps://www.blogger.com/profile/04935197246756840967noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8717859118145472902010-11-04T19:42:11.764-05:002010-11-04T19:42:11.764-05:00I think the difficulty of this problem is to some ...I think the difficulty of this problem is to some degree a question of learning theory (and then a question of human communication). The problem is one of finding a hypothesis that describes the examples that we're presented with and generalizes to unseen examples. As we all know, if the complexity of the hypothesis space is virtually unbounded, the problem is virtually impossible. <br /><br />Here the problem can be posed in a natural and simple hypothesis space. After all there is a very small FSA that decides membership in the sequence, were the sequence written out in English. The difficulty comes from subtly suggesting the wrong hypothesis space. The problem is posed in a mathematical language and in a mathematical context, which suggests the usual hypothesis space for these sequence problems: simple algebraic functions. Even extensions of this space however will lead you nowhere - any valid description is ridiculously complicated. Were the problem posed as a membership question in a sequence of strings, then we would have the right hint as to what kind of pattern we're looking for.<br /><br />So in a few words, the difficulty comes from posing the question in one language (by writing out the sequence in digits) even though the simplest correct hypothesis works on a "translation" (and an entirely human one) into another language.Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16377532385043686492010-10-27T16:13:34.486-05:002010-10-27T16:13:34.486-05:00When I first saw this puzzle, my mathematical mind...When I first saw this puzzle, my mathematical mind was stumped -- I couldn't even think of a hypothesis to try. Two hours later, I happened to think of it again, and the right idea popped into my head. Sometimes it helps to take a break.<br /><br />Some people would call this an exercise in creative thinking. In my case, I think it was more a function of what kinds of similar puzzles I had been exposed to in the past.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46147132201819533872010-10-25T12:04:12.191-05:002010-10-25T12:04:12.191-05:00One of my bright High School Students
got it right...One of my bright High School Students<br />got it right with the hint<br />`This puzzle is really stupid.''<br /><br />ANYWAY, based on all of your responses<br />I think we conclude that this is a hard puzzle. Whether or not it is a stupid one is a matter of opinion.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63126387016078170212010-10-22T02:41:42.690-05:002010-10-22T02:41:42.690-05:00I cant solve it.I cant solve it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13327763690605134612010-10-21T15:12:12.899-05:002010-10-21T15:12:12.899-05:00I guessed right, but after considerable trial and ...I guessed right, but after considerable trial and error. I tried virtually everything I could think of before I started writing the numbers out in English..I am not entirely sure what is the use of this I am also not sure how this problem could be classified as hard/easy? This problem may be extraordinarily hard<br />(if we are only looking at eban) for someone who is not familiar with English.Shishirhttps://www.blogger.com/profile/18028907708692265173noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51256594222558048552010-10-20T15:25:54.613-05:002010-10-20T15:25:54.613-05:00My great Niece guessed 2000 (the correct next valu...My great Niece guessed 2000 (the correct next value) and 2002 (the correct next<br />value after that).<br /><br />How did she do that?<br /><br />I do not know.<br /><br />GASARCHGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20593202107035010442010-10-20T11:39:43.377-05:002010-10-20T11:39:43.377-05:00x=1/3
y=pi
What do you mean it's not an 18th-...x=1/3<br />y=pi<br /><br />What do you mean it's not an 18th-degree polynomial?CharlesMartelnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32410226555983151162010-10-19T01:36:56.950-05:002010-10-19T01:36:56.950-05:00lance and bill are a mathematician so obviously he...lance and bill are a mathematician so obviously he knows what he id doing when he moderates aka they are objective either way.<br /><br />but please bill, can you block more or tell us whether you are busy nowadays. what's going on ? and lance has promised us updates on his book progresss .... wat's going on there ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32740076105127979822010-10-18T02:41:34.380-05:002010-10-18T02:41:34.380-05:00moderation is not free market oriented i am unsure...moderation is not free market oriented i am unsure whether this will be as good as it is believed to be.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16198043517055352502010-10-17T23:06:34.927-05:002010-10-17T23:06:34.927-05:00bravo, to moderation! now we will have to wait dec...bravo, to moderation! now we will have to wait decades for comments to appear.<br /><br />moderation hampers the natural flow of evolution.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22450481385554396492010-10-17T23:01:52.475-05:002010-10-17T23:01:52.475-05:00I have a general question.
Why does the overall q...I have a general question.<br /><br />Why does the overall quality of a blog decline as time progresses ? I mean, look at this block, some of the comments are funny while others are clearly meant to instigate chaos in my home country china. WE CHINESE DO NOT ALLOW FOREIGNERS TO INTERVENE IN OUR INTERNAL AFFAIRS, DONT U UNDERSTAND ? IT IS OUR COUNTRY AND FOREIGNERS DONT UNDERSTAND US.<br /><br />I mean how could they understand tian-an-men square incident where we gave orders to wheel tanks over our very own children and then are ashamed to admit such an incidence thus eradicate any documents pertaining to that event. How could foreigners understand this ? They don't. Tiananmen Square never happened. Taiwan is part of mainland china and the U.S. can't do anything about it. We will lurke the Taiwanese into mainland china. We have our own devilous tactics.<br /><br />And Tibet will always be suppressed by china, coz we are the stronger nation. We will never grant them any human rights. It's own triple T secret society.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80256818704337090242010-10-17T18:40:01.618-05:002010-10-17T18:40:01.618-05:00"if this is really the answer, I saw it in 10..."if this is really the answer, I saw it in 10 sec :)"<br /><br />it isn't the answerAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22593645779073652752010-10-17T15:06:09.843-05:002010-10-17T15:06:09.843-05:0066,70.
look at the last digts always. 0 2 4 6
the...66,70.<br /><br />look at the last digts always. 0 2 4 6<br />the first digits increase from one to one.<br /><br />60,62,64,66,70<br /><br />if this is really the answer, I saw it in 10 sec :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49138895023135278762010-10-17T00:12:29.188-05:002010-10-17T00:12:29.188-05:00I couldn't solve it.
Never seen this type of p...I couldn't solve it.<br />Never seen this type of puzzle! Was on a completely wrong track!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18349085509086672072010-10-16T20:24:04.960-05:002010-10-16T20:24:04.960-05:00Laslo Lovasz wins the Kyoto prize!Laslo Lovasz wins the Kyoto prize!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46233588736118223652010-10-15T19:18:28.738-05:002010-10-15T19:18:28.738-05:00Could not figure it out in five minutes ... was an...Could not figure it out in five minutes ... was annoyed when I looked up the "algorithm" ... (because it was unlikely to be of further utility in the enterprises that I care about). <br /><br />On the other hand, certainly there are some mathematical jobs where this problem (or a similar one) might legitimately be posed on <a href="http://www.nsa.gov/careers/opportunities_4_u/students/undergraduate/dsp.shtml" rel="nofollow">a job interview or aptitude test</a>.<br /><br />Within the context of such an aptitude examination, pretty much any mathematician's chances of solving this particular problem would be enhanced ... <br /><br />... and so perhaps this is one of the (many) mathematical questions regarding which a diversity of opinion is to be expected and welcomed.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20766242277008720902010-10-15T18:53:30.524-05:002010-10-15T18:53:30.524-05:00I solved it without any helpI solved it without any helpAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67323492971172038022010-10-15T18:19:57.124-05:002010-10-15T18:19:57.124-05:00I was unable to solve it.
I know an interesting an...I was unable to solve it.<br />I know an interesting anecdote related to the problem. Warning:<br />It contains MAJOR SPOILERS about the problem. I posted it as a comment here:<br /><br />http://blog.computationalcomplexity.org/2002/08/complexity-class-of-week-s2p.htmlTomnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66843868439837220362010-10-15T17:26:31.235-05:002010-10-15T17:26:31.235-05:00I was unable to solve it.I was unable to solve it.Mark Citynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68875770775486766252010-10-15T16:37:32.380-05:002010-10-15T16:37:32.380-05:00Are these all numbers that don't have an "...Are these all numbers that don't have an "e" in English spelling?Anonymousnoreply@blogger.com