|
|
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 NP-completeness. Knowing whether a problem is NP-complete
>> 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
"NP-complete" means "pretty darn hard."
Someone already pointed out: P <= NP <= EXP and P < EXP. But using the
term "NP-complete" lets us add: If P != NP, then NP-Complete 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 one-way
functions don't exist, and public-key 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 "NP-complete" 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
|
|
