tag:blogger.com,1999:blog-12932458.post112757417437419231..comments2023-09-29T09:03:36.236-05:00Comments on Logicomp: P vs. NP: let's think out loudanthonywlinhttp://www.blogger.com/profile/07618509800342861247noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-12932458.post-1129164352027381092005-10-12T19:45:00.000-05:002005-10-12T19:45:00.000-05:00Yes, I agree that what you mentioned is a disconce...Yes, I agree that what you mentioned is a disconcerting fact, at least in theory. In practice, as you mentioned before, this algorithm might be, whether it be polynomial or not, just too slow to invert the RSA function. So, it might not matter in the end.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1129163504998052222005-10-12T19:31:00.000-05:002005-10-12T19:31:00.000-05:00Anthony: at the end of the day, I'd make it a poin...Anthony: at the end of the day, I'd make it a point to include discrete logarithm and Nash equilibria for bimatrix games, too. Well, perhaps with emphasis on factoring and discrete logarithm... it seems mildly disconcerting that we know how to do it, given it can be done, since this is the stuff cryptosystems are made of...<BR/><BR/>Anyway, the decision problem you stated works. You can even get away with {(n,k): n has a prime factor < k} ... a Turing reduction is just binary search, divide, and repeat.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1129060954898486702005-10-11T15:02:00.000-05:002005-10-11T15:02:00.000-05:00Brendan: You're right that the proof in the case o...Brendan: You're right that the proof in the case of factoring is easy. Actually, since we have a poly-time algo for primality, we only need to know that factoring is an TFNP problem, and Levin's clever enumeration trick will work. In this case, the verifier will just take a decomposition of x into a sequence of numbers, and test whether or not this is *the* (up to ordering) valid decomposition of x into products of prime factors.<BR/><BR/>Also, yes, it doesn't seem obvious how this problem generalizes to all problems in NP intersects coNP. I'll this about this more carefully. Thanks also for the reference.<BR/><BR/>Well ... I guess at the end of the day what really matters is whether there is a poly-time algorithm for factoring ...<BR/><BR/>One last question: how do you turn factoring to a decision problem? Is the corresponding decision problem { (n,a,b) : n has a prime factor x with a < x < b }?anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1129019305659678722005-10-11T03:28:00.000-05:002005-10-11T03:28:00.000-05:00Anthony: properly, the question on the midterm was...Anthony: properly, the question on the midterm was to show this for the case of factoring; after the fact, it was noted that the result generalizes... I had been a little careless, and overstated how greatly the result generalizes. I'll discuss this at the end.<BR/><BR/>For the case of factoring, the problem isn't very difficult. Half of the trick is stepping through an enumeration of clocked polynomial-time TMs, and the other half makes use of the fact that we have certificates for both YES and NO instances. Run the kth TM to completion on the input string x to obtain f_k(x). Now, run the verifier algorithms on f_k(x); if the YES or NO instance verifier accepts, decide YES or NO, respectively. Otherwise, move to the k+1st TM in the enumeration.<BR/><BR/>We know that if factoring is in polynomial-time, then there is some K'th polynomial-time TM computing the factorization of any input n, factor(n) = f_K'(n) ... it's easy to design the YES/NO instance verifiers to take the factorization of the input as their certificates. Assuming that we've been clever about the enumeration, only enumerating up to TMs that have running time-bounds of degree at most d, then it's clear that our running time is O(K'n^d)=O(n^d), since K' is just a constant. <BR/><BR/>As I mentioned earlier, I was being pretty cavalier in stating the generalization of the problem: we do need to know the YES/NO verification algorithms, but perhaps more critically, we used the fact that the decision problem is polynomial-time equivalent to a function problem. <BR/><BR/>To be correct, the statement of the theorem should say that for any language L we have constructively shown to be in NP intersect coNP we can construct a TM M such that if the associated TFNP problem is in FP, then M decides L in polynomial time. ("the associated TFNP problem" is one that computes a witness of the appropriate type) It's clear also that we can construct a TM N that solves the associated TFNP problem, i.e., one that prints out the witness that satisfies one of the verifiers.<BR/><BR/>Clearly, if L is not polynomial-time decidable, then the associated TFNP problem is not in FP... we just happen to get the "iff" for factoring because we chose the decision problem specifically to guarantee that L in P implies the TFNP problem is in FP. This also happens to be true of most of the problems we're interested in contained in NP intersect coNP, since we're almost always studying polynomial-time equivalents of our function problems of interest... unfortunately, it's not clear whether or not it's true for all of NP intersect coNP. (sorry about that!!) <BR/><BR/>Anyway, this bugged me today, so I spent a while trying to track down the result. It does turn out to be Levin's work: there's a Russian version of the article, "Universal enumeration problems" from 1972 and apparently an English version "Universal sequential search problems" in Problems of Information Transmission,<BR/>9(3):265-266, from 1973.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1128993836097365872005-10-10T20:23:00.000-05:002005-10-10T20:23:00.000-05:00Brendan: ok, thanks. But, I guess more important t...Brendan: ok, thanks. But, I guess more important to me is the proof. How do you prove the result in the midterm exam? I guess it can't be that complicated.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1128965674975847132005-10-10T12:34:00.000-05:002005-10-10T12:34:00.000-05:00Anthony: I encountered it on a midterm exam, so un...Anthony: I encountered it on a midterm exam, so unfortunately I don't know where it was done first either... I'll let you know if I find out, though.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1128958818050020912005-10-10T10:40:00.000-05:002005-10-10T10:40:00.000-05:00Brendan, thanks for your comments. Could you pleas...Brendan, thanks for your comments. Could you please tell me where you encountered that result "that L in NP intersects co-NP, we know an algorithm for L iff L is in P"? Please let me know which paper proved this. I have heard of this result (I think it was proved by Levin) but I couldn't find which paper it was proven in.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1128709962258506172005-10-07T13:32:00.000-05:002005-10-07T13:32:00.000-05:00While you're on the topic of inefficient algorithm...While you're on the topic of inefficient algorithms, a tangentially related but slightly offtopic result is that for any language L that we've shown to be in NP intersect coNP by actually giving the nondeterministic algorithms, we know an algorithm for L that is polynomial-time iff L is in P. Of course, nobody uses this algorithm in practice to try to solve factoring (for example) since it starts off with "take an enumeration of all polynomial-time TMs..." Anyhow, this is one method we can use to get at "inefficient polynomial time algorithms." It's true that there don't seem to be many of them... or at least, they aren't talked about much since they aren't algorithms of any particular practical value. <BR/><BR/>Still, if (for example) we managed to show a formal independence result for some language, such an algorithm might be useful, and would be pretty much the only option for (potentially) finding exact solutions in polynomial time... one could imagine augmenting the algorithm with a counter that keeps track of where in the enumeration it last was, to try to cut down on the overhead. You wouldn't (by hypothesis) be able to show that the algorithm was polynomial-time, but if the counter remained at the same index in the enumeration after many instances, you could take that as a source of "inductive evidence" that the algorithm would be polynomial time.<BR/><BR/>Slightly more on-topic now, it's worth noting that lower bounds are often so hard to prove because they simply aren't true. (ex: a circuit computing the negation of three input variables using only two NOT gates... as the statement suggests, there are many others, too.) Of course, I haven't said much since you can take this statement in two ways:<BR/><BR/>i) we haven't shown P != NP because we haven't hit upon the right lower bound<BR/><BR/>ii) we haven't shown P != NP because it isn't true<BR/><BR/>Oh well!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1127783985535717382005-09-26T20:19:00.000-05:002005-09-26T20:19:00.000-05:00The other similar story is regarding Huffman codin...The other similar story is regarding Huffman coding. I can't recall the exact story, as Alistair Moffat (one professor in my ex comp. sci. department who works on compression) told me. The name of the lucky student this time is Huffman. Actually, the same thing happened with Donald Knuth (he was assigned a challenge (which turned out to be an open problem) with the promise that he would get an A+ immediately. So, he ended up solving the problem and not attending the rest of the course!)<BR/><BR/>Anyway, I do agree with you on your last point, as long as the odds are not something like 80/20 in favour of P not equal NP.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1127743358050106802005-09-26T09:02:00.000-05:002005-09-26T09:02:00.000-05:00On the second reading, it sounded like I suggested...On the second reading, it sounded like I suggested P = NP. So, I change the word 'very' on the last paragraph to 'equally'. I hope this makes my reader happy.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1127740267350781932005-09-26T08:11:00.000-05:002005-09-26T08:11:00.000-05:00BTW: the proof that NSPACE is closed under complem...BTW: the proof that NSPACE is closed under complementation given by Szelepcsenyi turns out to be unexpectedly simple.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1127739899691802712005-09-26T08:04:00.000-05:002005-09-26T08:04:00.000-05:00Kenny, you're missing the point. I by no means sug...Kenny, you're missing the point. I by no means suggested that P=NP. The main point of the argument is that to believe P=NP is as just reasonable as to believe P is different from NP. I'm also suggesting that one has to be impartial if one wants to resolve the P vs. NP problem. One very good example is the resolution of the question whether NSPACE is closed under complementation. It was open for 25 years until an undergrad (Szelepcsenyi), who was given this problem as a challenge and totally unaware that the problem was open, solved it positively (also independently resolved by Immerman at around the same time). Almost everybody conjectured the negation of this statement. I'm sure one can easily come up with other examples.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.com