Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: On NP Completeness and Intractability
Replies: 90   Last Post: Nov 1, 2005 8:08 PM

 Messages: [ Previous | Next ]
 Arthur J. O'Dwyer Posts: 91 Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 27, 2005 5:13 PM

On Thu, 27 Oct 2005, Randy wrote:
> Joe Hendrix wrote:
>> This suggests you still don't understand what NP complete and NP hard
>> mean. Algorithms are not NP complete, problems are. Algorithms may
>> have a polynomial time running time, an exponential time, or something
>> even worse. A good algorithm doesn't even have to always terminate to
>> be useful -- Knuth-Bendix completion is a good example of an important
>> algorithm that does not.

(Tangent: According to my lexicon, if a method doesn't terminate, it's
not an "algorithm." Algorithms terminate in finite time, which is why
they're so useful. :) Replace "algorithm" with "method" or "procedure"
in your sentence, and I agree completely.)

> Is the issue here one of solution space vs problem space, algorithm vs
> problem description, thereby necessitating and justifying the need for
> dissimilar KINDS of complexity? If so, that explains a lot. In
> essence, CC exists because it's meaningless to equate complexity
> measures in the problem and solution space. Which is what I've been
> doing, unsuccessfully.

Exactly!

> I won't dispute that finding a problem to be NPC has value. But simply
> quantifying its theta asymptotic complexity would seem to be equally
> valuable, seemingly more so, and without the added burden of proving
> that the problem's in NP.
>
> Or am I still confusing apples (problems) with oranges (solutions)?

Yes, you are. /Algorithms/ have asymptotic complexity. /Problems/ do
not.
Now, it's often[1] possible to talk about the /best possible/ algorithm
to solve a given problem, and then talk about that algorithm's theta
complexity, which is what you're wanting to do. But in the kind of
computer science we're talking about, it's hardly ever obvious whether
you've found the /best possible/ algorithm --- and if you haven't, then
it's no use talking about its complexity.

Example: Suppose the problem is "sort a list of integers." What is the
complexity of this problem?
Alice thinks, "Aha! Sorting the list requires comparing each pair of
elements, so the complexity of the problem is O(n^2)." Alice is WRONG.
Bob thinks, "Aha! Shell-sort is an algorithm that sorts a list in
something like O(n^1.5) time, so the problem is about O(n^1.5)."
Bob is right about the complexity of Shell sort, but WRONG about the
complexity of the underlying problem. Shell sort is simply not the
best possible algorithm for the problem.
The RIGHT answer is O(n lg n), and it takes a surprising amount of
math to prove that. Just imagine how much math it might take to prove
the complexity of a problem that's actually hard!

> In other words, isn't proving NPC overkill if all you want to do is
> characterize a problem? Wouldn't it be equally effective to identify a
> problem's worst case runtime

This is the flaw in your line of argument --- problems don't /have/
runtime. /Algorithms/ have runtime.
(A second problem is that I can make the worst-case runtime as bad as
I want, just by picking a really stupid algorithm to solve the problem.)

By the way, many people have mentioned the existence of problems in EXP
but not in NP, but I don't think anyone's given an example yet. Here's a
trivial example: Given an integer N, print out all the integers between
1 and 2**N. That problem isn't in NP, because solutions can't be verified
in polytime --- it takes O(2**N) time just to read the solution in!

HTH,
-Arthur

[1] - I'm fairly sure there exist classes of problems with no "best"
solution, but merely an infinite family of solutions each of which is
better than the last. I don't have any examples, but I'd be interested
to see one.

Date Subject Author
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 Dr. David Kirkby
10/25/05 ianparker2@gmail.com
10/25/05 Pubkeybreaker
10/25/05 osmium
10/25/05 Pubkeybreaker
10/25/05 Willem
10/25/05 Bryan Olson
10/25/05 Willem
10/25/05 Ed Prochak
10/25/05 Dr. David Kirkby
10/25/05 Gene
10/25/05 MartDowd
10/25/05 RobertSzefler
10/25/05 Dr. David Kirkby
10/25/05 Pubkeybreaker
10/25/05 Wim Benthem
10/26/05 RobertSzefler
10/25/05 KP Bhat
10/25/05 stephen@nomail.com
10/25/05 tchow@lsa.umich.edu
10/25/05 googmeister@gmail.com
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/27/05 stephen@nomail.com
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 C6L1V@shaw.ca
10/25/05 stephen@nomail.com
10/25/05 Wim Benthem
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/26/05 Randy
10/27/05 Arthur J. O'Dwyer
10/27/05 Randy
10/27/05 Willem
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 tchow@lsa.umich.edu
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Arthur J. O'Dwyer
10/27/05 googmeister@gmail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 Arthur J. O'Dwyer
10/28/05 Joe Hendrix
10/28/05 Ben Rudiak-Gould
10/28/05 Bryan Olson
10/28/05 Pekka Orponen
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/25/05 tchow@lsa.umich.edu
10/25/05 Michael J. Hennebry
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/25/05 Willem
10/25/05 Arthur J. O'Dwyer
10/25/05 googmeister@gmail.com
10/31/05 Oliver Wong
10/31/05 Robert Israel
11/1/05 Willem
11/1/05 googmeister@gmail.com
11/1/05 Willem
11/1/05 Torkel Franzen
11/1/05 googmeister@gmail.com
11/1/05 Oliver Wong
11/1/05 Willem
11/1/05 Robert Israel
10/26/05 Randy
10/26/05 stephen@nomail.com
10/26/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/25/05 Pat Farrell
10/25/05 Bryan Olson