tag:blogger.com,1999:blog-11788780.post825381545563913592..comments2017-07-23T15:24:01.936-07:00Comments on JJinuxLand: Computer Science: NP-complete Problems are Really NP-completeShannon -jj Behrensnoreply@blogger.comBlogger15125tag:blogger.com,1999:blog-11788780.post-12517753180530407212011-12-01T14:54:36.377-08:002011-12-01T14:54:36.377-08:00Kelly, thanks for your comment. Two points:
* I...Kelly, thanks for your comment. Two points:<br /><br /> * I don't think you can do a binary search since the response is "yes" or "no", not "you're too high" or "you're too low".<br /><br /> * It was a mistake to use 32 bit unsigned ints. Vincent pointed out the flaw in that. I'd suggest using an N-tuple of arbitrarily large whole numbers.Shannon -jj Behrenshttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-33222485109999585042011-11-30T09:33:38.087-08:002011-11-30T09:33:38.087-08:00Hi JJ, just to chime in, I think your assertion th...Hi JJ, just to chime in, I think your assertion that it takes "O(A^n) for some constant A" operations to find the answer is incorrect. Consider that to guess one 32-bit integer, you need a maximum of 32 operations, thanks to the power of binary search. So that is constant. So if you had 2 32-bit ints to guess, you would need 2*32 operations; for 3 32-bit ints, you would need 3*32 operations at max. So, for N 32-bit ints, you could guess the answer in N*32 operations. So, in big-O notation, it takes O(N) operations to find the answer; it isn't polynomial time, but linear with N.Kelly Yanceyhttps://www.blogger.com/profile/08648597728708472240noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-52229629177614876362011-11-30T04:06:25.891-08:002011-11-30T04:06:25.891-08:00Fair enough.Fair enough.Bijan Parsiahttps://www.blogger.com/profile/07024418532546914722noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-85507771452769798432011-11-29T17:18:24.307-08:002011-11-29T17:18:24.307-08:00Bijan, thanks for the book recommendation. I'...Bijan, thanks for the book recommendation. I'll try my best not to kook out. I don't have any problem with special relativity. When I say "stupidly clever", but what I mean is that sometimes a hard problem has a simple, but clever solution. "Elegant" is probably a better word. The reason I haven't invested the time to learn complexity theory properly is that I just don't have enough free time to do it right now. The reason I posted a totally half-baked, uninformed solution on my blog is that if it did happen to have some nugget of usefulness, someone else would probably run with it, and if it didn't happen to have any nugget of usefulness, I don't mind looking stupid sometimes--it's good to keep my ego in check. Also, I knew there were smarter people than me who read my blog who might be able to explain things to me in terms even I could understand.Shannon -jj Behrenshttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-68280316302420112302011-11-29T17:10:20.211-08:002011-11-29T17:10:20.211-08:00Er...I definitely wouldn't characterize either...Er...I definitely wouldn't characterize either the halting problem or its proof as "stupidly clever". If you look at the history of early 20th century logic (for example) it fits in (albeit as a serious advance/result). See Goedel's incompleteness theorem.<br /><br />I don't know how else to put that I think your approach, esp. in the way you double down in this last comment, is not likely to lead you to a good understanding of the issues (or of complexity theory). You also are running the risk of kooking out. ("Trying to be stupidly clever...like the halting problem" is pretty close to "I have a proof that special relativity is false" or taking your hot cousin to the prom or "I'm like Galileo and you are like the pope, oppressing my scientific geniusness!!!" I don't think you are *there*, just uncomfortably close by.)<br /><br />I think the P = NP question is one of the most amazing and fun things to explore, so I strongly encourage you to do so. I just rather suspect that the current approach is particularly efficient (e.g., afaict, you aren't even in the ballpark; cf my other comment).<br /><br />I find the Gary and Johnson complexity book to be really nice for getting into the groove.Bijan Parsiahttps://www.blogger.com/profile/07024418532546914722noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-86823695107316679182011-11-29T16:07:11.677-08:002011-11-29T16:07:11.677-08:00Guys, thanks for your comments. It'll take me...Guys, thanks for your comments. It'll take me a while to digest them all.<br /><br />Bijan, "stupidly clever" is what I was aiming for. The proof for the halting problem was "stupidly clever."Shannon -jj Behrenshttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-23028305793517462482011-11-26T04:04:55.408-08:002011-11-26T04:04:55.408-08:00First a general methodological point: Given the tr...First a general methodological point: Given the triviality and obviousness of your approach, your own self-awareness of your lack of grip on the problem ("I haven't seen the proof for it, but I've also heard that if you could prove that one NP-complete problem does not have a polynomial-time solution to it, then that would prove that none of them have a polynomial-time solution to them."), then the overwhelming odds are that your approach is hugely flawed. A good exercise is to try to break it yourself. Indeed, in general, this is a <i>better</i> approach than trying to defend it against other people breaking it (though that's not unreasonable). Confirmation bias alone is a big danger and you learn more about what makes the problem <i>and your proposed solution</i> tick by finding flaws.<br /><br />There are a lot of problems with the proof (many have been pointed out), but I'd start with:<br /><br />"Hence, I can verify a solution in polynomial-time (it takes me O(n) number of int comparisons to verify a solution)."<br /><br />There are a number of issues other commenters have raise, but, here's the one I think is key:<br /><br />Who is doing the verifying? If it's the person (really *process*) with antecedent knowledge of the answer, then they aren't really verifying the the answer, they are doing a look up. Let P be the proposed solver of this problem, V be an <i>independent</i> verifier and Y be you, the person who made up the number. V is independent in the sense that there is no communication between V and Y other than the knowledge of what the problem is (i.e., guess a randomly generated number).<br /><br />P provides a possible answer...how does V verify it? It can't! There's no verifying that the answer is right because there's no way to tell what the right answer is except by asking Y. Once we get an answer from Y we can <i>compare</i> answers in linear time. But V doesn't have any way of knowing that Y didn't lie! Thus it cannot verify the answer.<br /><br />Imagine there were Y1 and Y2, and let N=2. It's highly likely that Y1 and Y2 will generate different tuples and suppose that is the case. Now P is told, "Solve this problem for N=2". Which answer is the right answer such that V should confirm it? Y1's or Y2's? There's no being right here. Thus this isn't the right kind of problem. (Note, we know of problems that are <i>strictly harder</i> than NP-COMPLETE problems. So you have to be careful that you haven't shown that one of <i>them</i> doesn't have a polynomial solution...that would just tell us what we already know.)Bijan Parsiahttps://www.blogger.com/profile/07024418532546914722noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-47589364678381530712011-11-25T21:49:10.883-08:002011-11-25T21:49:10.883-08:001. Again, "what the key is" is not a yes...1. Again, "what the key is" is not a yes/no question. You can instead use something like "given plain text message, encrypted message, numbers i and m, is the i-th element of the key greater than m?"<br /><br />2. For example, say your algorithm just XORs plain text with repeated copies of the key. It does satisfy your conditions (you can use any n-tuple as the key and there is no more than 1 key which converts the given plain text to the given encrypted text), but it's trivial to find the key: just XOR plain and encrypted messages.<br /><br />3. So you need to pick some algorithm and prove that there is basically no other way to find the key except by guessing. And well, so far nobody has been able to do that!Alexey Romanovhttps://www.blogger.com/profile/04414745317669007614noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-87723179734670161392011-11-25T19:48:11.159-08:002011-11-25T19:48:11.159-08:00For a problem to be NP complete it is necessary to...For a problem to be NP complete it is necessary to show the reduction in both directions: show that the problem is no easier than other NP-Complete problems (convert a known NPC to this problem in poly time) and no harder as well (convert this problem to a known NPC in poly time).<br /><br />I think you've only given a single direction.Paul Du Boishttps://www.blogger.com/profile/12610975665542295591noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-73950366159556729672011-11-25T19:26:29.741-08:002011-11-25T19:26:29.741-08:00Just like to point out that using tuple is no diff...Just like to point out that using tuple is no different that just guessing a any integer. The set of all possible integer tuples is the same size as the set of integers really they are the same size the set of reals is larger though.<br /><br />Is N know to the guesser?<br /><br />Not sure if this is a "decision" problem but once you guess a no more that is bigger that the solution , chose the largest 32bit integer, then the problem is polynomial. Just count 1,2,3,4,5 ( keeping in mind that the tuples a the same size as the integers and therefor can be ordered/sorted/counted.<br />http://en.wikipedia.org/wiki/Countable_setVincenthttps://www.blogger.com/profile/10012339349739274016noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-32902121924809054822011-11-25T18:50:56.345-08:002011-11-25T18:50:56.345-08:00Alexey, thanks a lot for your response. Let me se...Alexey, thanks a lot for your response. Let me see if I can turn it into a decision problem.<br /><br />Let's say I have an encrypted message. I already know what it's supposed to say, and I already know the algorithm that was used to encrypt it. What I don't know is the key used to encrypt it. My goal is to find the key so that I can decrypt other messages.<br /><br />The key happens to be an n-tuple of integers. The algorithm is such that there is exactly one n-tuple that can be used to decrypt the message in such a matter that I end up with the original message. Furthermore, the algorithm is such that the person who picked the key had the freedom to choose any n-tuple of 32-bit, unsigned integers.<br /><br />Given all that I know, I must decide what the key is.Shannon -jj Behrenshttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-64216989105657743772011-11-25T15:37:45.303-08:002011-11-25T15:37:45.303-08:00The problem with your problem is that it isn't...The problem with your problem is that it isn't a decision problem :)<br /><br />A decision problem for tuples of integers is basically just a set of such tuples. And given a tuple, you must determine whether it's in the set. Note that there is nothing adversarial here: you can't keep the set "secret".<br /><br />So, if the set only contains one tuple, the algorithm is simple: compare argument tuple with this tuple; if they are the same, return "yes", otherwise return "no". This problem is in P (and even in L).Alexey Romanovhttps://www.blogger.com/profile/04414745317669007614noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-49915093832795891882011-11-25T15:35:56.642-08:002011-11-25T15:35:56.642-08:00Shawn Drape said:
I think you also have to prove ...Shawn Drape said:<br /><br />I think you also have to prove that your proposed problem can be transformed into a known NP-Complete problem in polynomial time. Use the traveling salesman as a target.<br /><br />To which I responded:<br /><br />Hmm, here is a way to convert the problem into the traveling salesman problem. Number each of the cities. Your trip among the cities is a tuple of numbers. If the cost of each trip between cities is completely random (i.e. if you don't assume that close cities are cheaper to travel between than distant cities), then the optimal solution is an N-tuple of city numbers. Either way, you have to at least partially examine every possible solution.Shannon -jj Behrenshttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-65163585537338390632011-11-25T15:26:30.420-08:002011-11-25T15:26:30.420-08:00When I said "lucky", I was just trying t...When I said "lucky", I was just trying to be funny. There aren't any lemmas or theorems that will help you figure out which random n-tuple I have in mind other than brute forcing it. When you try one n-tuple, I tell you that you're either wrong or right. I don't give you any information that will help you get substantially closer to the right answer. (For instance, I don't tell you if you're partially right.)Shannon -jj Behrenshttps://www.blogger.com/profile/03270879497119114175noreply@blogger.comtag:blogger.com,1999:blog-11788780.post-83638523804898780742011-11-25T14:35:16.874-08:002011-11-25T14:35:16.874-08:00Just one thought - you're saying that the only...Just one thought - you're saying that the only other alternative to brute forcing it is to get "lucky." I think you're being disingenuous as to what "lucky" is here.<br />Everyone studying these problems has full access to every other lemma and theorem out there. Getting "lucky" is often a simple matter of combining several of these lemmas and theorems together in interesting new ways.<br /><br />It's important to note that "lucky" is not the same as "trial and error" or "random."Aaronhttp://unbounce.comnoreply@blogger.com