NP-completeness (spinoff from MrDeath's thread)

Miscellaneous and Personal Stuff I Must Share
1

In reference to a question brought up in this thread, I’m going to attempt to define NP-completeness.

First we need some notion of the running time of an algorithm. In order to do that, we need some measure of input size. This varies by problem (a concept I’m not going to define here), so we’ll just call it n.

The running time of a particular algorithm can be expressed exactly as some function of the input size. Let’s call it f(n). We’re very rarely interested in the specifics of f, so we make the following definition:

O(f(n)) is the set of all functions g(n) that are less than c*f(n) whenever n > n[sub]0[/sub], for some positive constants c and n[sub]0[/sub]. O(f(n)) is read “big-oh of f(n)”.

So instead of being very precise, we say that the running time of an algorithm is O(g(n)) for some suitable g(n). Equivalently, we say that g(n) is an asymptotic upper bound for the algorithm. There’s a similar concept of an asymptotic lower bound, but that’s not really important here.

Some algorithms are O(n[sup]k[/sup]) for some k. These algorithms are said to run in polynomial time.

In addition, sometimes we want to consider how long it takes to verify a solution. This means that, instead of calculating the solution ourselves, we are given a potential solution, and need to determine whether it is an actual solution.

The set of all problems that can be solved in polynomial time is called P. The set of all problems that can be verified in polynomial time is called NP. (If I told you what NP stands for, you’d just be confused. So don’t worry about it.) It should be fairly clear that every problem in P is also in NP.

Now here’s the thing: there are some problems that are as hard as anything in NP, and we can use algorithms that solve these problems to solve any problem in NP. More formally, an instance of any problem in NP can reduced (or transformed) into an instance of one of these problems, and then we can use a solver for that problem. Such a problem is called NP-hard (meaning that it’s at least as hard as anything in NP). When an NP-hard problem is in NP, we call it NP-complete.

One technical detail I omit is that all the problems we consider can be expressed as yes-no questions. This is sufficient to cover all possible problems.

Make sense? Questions?

2

Sorry, I still don’t get it. (which I attribute to my lack of neural connections, not your excellent description.) Could you give some examples of problems in each of the subsets, i.e. an NP-hard problem, an NP-complete problem, etc. And reasoning to why they are in the categroy they are in.

On a side issue, you talk about running time. I know about complexity relating to time and space. Is it fair to say that the concept of NP-completeness relates only to running time and not to required space?

3

To answer your second question first, NP-completeness applies only to running time. There is a similar complexity class for problems that can be solved/verified in polynomial time (it turns out that there’s no distinction when you’re talking about space), and it’s called PSPACE.

I’m gonna have to get back to you on the examples, cause it’s late, and I’m tired. Meanwhile, I recommend you do a search for “NP complete problems” and “NP hard problems”. There are a lot of sites out there that already have great descriptions; I’ll see if I can’t find some tomorrow.

Of course, if you were to reference a specific site and explain exactly what parts you had problems with, it would help me a lot. :slight_smile:

Lastly, I can give lots of examples of NP-complete problems, but giving an example of a problem that’s NP-hard and outside of NP might be a little tough. Such problems are hard to come by and generally not related to anything commonsensical (although I’ve got an idea of one; we’ll see how that goes).

4

And of course, don’t be discouraged because you don’t get it at first. This stuff is so tough that we still don’t know the basics of it (e.g., it’s not known whether P = NP).

5

Well, there’s a book that’s been beside my bed for about five years (well, there’s a small bookshelf of maybe 50 books beside my bed, but I drift), that I pick up occasionally. It’s called Computational Complexity (Addison Wesley, 1994) by Papadimitriou. I’m told it’s a standard of sorts. So there’s a specific site. Now as to what parts I had problems with, well they begin somewhere around chapter 2 or 3 or 4, I’ll have to look it up.

I already know the real answer to this: Go do some research and figure it out. I guess I was just hoping for a quick no-effort solution.

Back in your original post:

check.

check.

Here’s where the problems begin. Define “as hard as anything in NP”. I assume this means "rank all of the problems in NP by length of time required to solve, and look at the lengthiest ones ". True?

Do I understand that problems of this sort (and only problems of this sort) are called “NP-hard”?

How? An example would go far.

If I understood above (that the definition of an NP-hard problem is one that is as hard as it gets in NP), then by definition, aren’t all NP-hard problems in NP? (Your last statement seems to imply that they aren’t, so which bad exit did I get off on?)

6

Well, I don’t have access to a copy of Papadimitriou’s book, but I’ll do what I can.

I assume you have some exposure to reductions between problems, but I’m going to go ahead and define them here. I’m doing this all from memory, so if I get something wrong, go easy on me. :slight_smile:

Let’s start with some basic definitions. We will be concerned with strings, which are just sequences of characters. A language is a set of strings. A problem is just another word for a language. A problem instance is a string that might be a member of a given language, and solving the problem consists of determining the membership in that language of the given string.

When we are asked to verify that a string is in a problem, we are given a “certificate”, which is thought of as an explanation of why it is. For instance, if we’re trying to verify that a graph has a Hamiltonian circuit, the certificate would be a list of the vertices on that circuit. That’s not important, but I thought I’d mention it just for completeness.

Anyway, a reduction is a mapping between two languages which preserves membership. More formally, a function f: A -> B is a reduction from A to B whenever a is an element of A if and only if f(a) is an element of B. Does that make sense?

So a problem B is NP-hard if, for every problem A in NP, there is a reduction from A to B and that reduction can be computed in polynomial time. The set of NP-complete problems is the intersection of NP and NP-hard.

I need a textbook to give an example, so I should be able to find something tonight. Meanwhile, does this help?

7

Are there problems which are NP-hard, which are not NP-complete?

8

Oh yes, infinitely many of them. I believe (but am not 100% sure) that any problem outside of NP is NP-hard. Since an NP-complete problem must be in NP, these problems are definitely not NP-complete.