
Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 12:08 AM


On Wed, 26 Oct 2005, Randy wrote: > tchow@lsa.umich.edu wrote: >> However, I don't think that it's quite true to say that all of complexity >> theory is irrelevant to those who are interested only in algorithms. I >> don't think that any practitioner can afford to be completely ignorant of >> the concept of NPcompleteness. Knowing whether a problem is NPcomplete >> provides extremely valuable guidance in choosing an algorithmic approach >> to it.
Or even not knowing. For example, if I've got a problem that looks a lot like Traveling Salesman, I might try to "reduce" it to Traveling Salesman and use one of the known heuristic methods to get an approximate solution, rather than trying to come up with a homebrewed polytime solution that probably doesn't exist. In other words, I think it's safe in (most) practice to assume that "NPcomplete" means "pretty darn hard."
Someone already pointed out: P <= NP <= EXP and P < EXP. But using the term "NPcomplete" lets us add: If P != NP, then NPComplete and P are disjoint. This is very useful!
Note that this is /not/ true of EXP  you can't assume that "exponential" means "pretty darn hard," because all problems with polytime algorithms also have exponential algorithms, and it's not usually clear whether a given exponential algorithm can be replaced by a simpler polytime one. (For example, computing the shortest path from start to finish in a graph with N edges has an exponential algorithm: list all the paths, and then take the shortest. But the problem isn't hard at all; it's in P.)
> I'm going to take your word for that. I guess I'm more doubtful now of > the merits of computational complexity (CC) outside of academia. I > appreciate the value in characterizing tasks that are in/feasible, as > folks in OR have done for eons. But is the subtlety captured by the > narrow definition of NP really practically useful or conceptually > constructive, beyond the simpler concept of exponential asymptotic > complexity and its concomitant infeasibility? If so, I don't see it.
One important aspect of "NP" versus "pretty darn hard" is that any solution to a problem in NP can be verified in polytime. Which is one of the major bases of modern cryptography  if P=NP, then oneway functions don't exist, and publickey cryptography fails. (I'm sure someone will correct me at length if I've misstated that.)
So cryptography is one of those "(most)"s I mentioned above  you can assume that "NPcomplete" means "impossible to crack," as long as you're assuming P!=NP... but if one day your assumption turns out to be wrong, all of a sudden you're not safe at all! ;)
> If I've gained anything from this thread, it's a greater feel for the > specificity of and a lesser feel for the utility of P vs. NP, and Hard > vs. Complete. I'm left with a much stronger sense that CC has less > relevance than I thought. If I came to appreciate the inadequacy of > exponentiality as compared to NP, that could change. But it seems I > don't, and the preceding conversation has left we with less patience or > confidence that clarity will ever be forthcoming.
What on earth don't you understand? It seems like you came into the discussion and said a lot of wrong things at once, and then everybody else replied and said, "No, that's wrong, here's what's right." And now you're saying that complexity analysis must be irrelevant to (something; it's unclear what). No offense, but it's coming off as "sour grapes."
Arthur

