Another NP Complete thread

[kromagnon]

The only difference is that this one is about pure anger.

This was my first semester as a computer science grad student, and I took a final for "Design and Analysis of Algorithms" and my professor decided to put an impossible question on the exam. The question was:

Explain an algorithm that always finds the optimal solution the Traveling Salesman problem in polynomial time.



AM I MISSING SOMETHING HERE?

I just left the question blank.... I hope thats the right answer

[davean]

We actually don't know if that is possible or not. You can still describe such an algorithm using an oracle ...

[lazarus89]

Perhaps some variant of this?

http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort

Obviously, this isn't a sorting problem, but the same general approach applies: massive parallelism, followed by hilarious usage of the "destroy universe" operation.

Apologies if that made no sense at all... I just pulled an all nighter.

[EvilSporkMan]

The only difference is that this one is about pure anger.

This was my first semester as a computer science grad student, and I took a final for "Design and Analysis of Algorithms" and my professor decided to put an impossible question on the exam. The question was:

Explain an algorithm that always finds the optimal solution the Traveling Salesman problem in polynomial time.



AM I MISSING SOMETHING HERE?

I just left the question blank.... I hope thats the right answer

Uh, the right answer is probably to explain why a successful answer to this question would earn you 1) a million dollars and 2) a Ph. D. on the spot, no doubt.

[arcoain]

lol. That reminds me of the time my English teacher put on my exam:
"What is the difference between three?"

[Nexus_1101]

This reminds me of when i was in school and i had one of those sets of questions that are all connected, you know.. where the answer from the first is in the second and the answer from the second is in the third and so on...
so i asked the teacher for an extra piece of paper and did about 3 sides of A4 rant about how stupid a thing it was to link questions because i loose lots of points if i get the first question wrong.

all i got back was the comment "this was not necessary for the answer of question X".

[EvanED]

Actually part of me thinks asking that question, giving credit for leaving it blank, amusing answers, etc., but taking off points if the person actually attempts it would be a reasonable, if somewhat sadistic, thing to do.

But then I think that we probably don't want to discourage people from thinking about hard problems even if they know it's hard, so that probably wouldn't be the best option.

[quintopia]

You could write this:
1. Take as input a weighted digraph.
2. ???
3. Profit!

[Nuage]

I think you are missing something It seems likely to me that what the professor was trying to get you to do was something with oracles. Note that he said "explain an algorithm," which I'm guessing is a less formal instruction than would be given if they actually wanted a full, formal, completely implementable, algorithm.

You probably were supposed to start with something Hamiltonian Circuit or graph covering, and then assume you had a poly-time oracle for that, and show how you could use such an oracle to solve this problem. That's been my experience in CS classes with questions worded like this. Notice that he doesn't say "don't use oracles, don't make assumptions, etc." He says "explain an algorithm that can do this in polynomial time," so it seems perfectly valid to me to say something like "we showed in class that this problem is NP-Complete via the reduction {blah}, but here's how you could do it given an oracle for {blah}," (basically just explaining the reduction again).

Did you cover the polynomial hierarchy at all? Things like P^NP - meaning the class of problems in P given an oracle for NP?

[Citizen K]

I think that question is to see if you really get what it means for a problem to be in NP -- that you can decide the problem in polynomial time if you're given a nondeterministic machine.

Though I'd have to sit down and think a bit to figure out exactly how best to respond to the question... are we talking about the decision version of the problem? (i.e. Given graph G and length L, is there a Hamiltonian circuit having length <= L?)

[Nuage]

that you can decide the problem in polynomial time if you're given a nondeterministic machine.

let's be correct here - the entire point is that there are multiple, completely equivalent, characterizations about what it means to be in NP.

[Citizen K]

True enough, though NP does take its name from the one I mentioned.

[necroforest]

You could write this:
1. Take as input a weighted digraph.
2. ???
3. Profit!

TSP is on weighted undirected complete graph. Although I guess you could come up with a variant for digraphs.

[Joeldi]

Okay, I've spent today reading up on this, and I get P, I get NP, and I get P ?= NP, but I cannot find a good explanation of what NP-Complete is. From what I read, it sounds like there is only 1 NP-Complete problem, and every other NP problem is just that one problem stacked on top of itself and described with different metaphors each time. But nothing I've read actually says that, everything just keeps on saying that there are >3000 completely different NP-Complete problems. Please for the love of god help me. Preferably with pictures and with as few Xs and Ys as possible.

[EvanED]

Okay, I've spent today reading up on this, and I get P, I get NP, and I get P ?= NP, but I cannot find a good explanation of what NP-Complete is. From what I read, it sounds like there is only 1 NP-Complete problem, and every other NP problem is just that one problem stacked on top of itself and described with different metaphors each time. But nothing I've read actually says that, everything just keeps on saying that there are >3000 completely different NP-Complete problems. Please for the love of god help me. Preferably with pictures and with as few Xs and Ys as possible.

There are many (technically an infinite number of) NP-complete problems. However, what they share is the following: if there is an efficient solution for any of them, there is an efficient solution for all of them. Furthermore, there is no harder problem which is still in NP.

The way this is typically proven is via the notion of a reduction. This is essentially a transformation of one problem into another, and perhaps a transformation of the answer back. (Technical note: this transformation has to be "easy", i.e. polynomial, for this to show completeness results.) For decision problems, the only things you can do to the answer is leave it the same or negate it.

A reduction of a problem A to a problem B takes the input of a problem in A, transforms it into an input to problem B, and then transforms the answer back. What this does is show that problem A is no harder than problem B, sometimes written A <= B.

If you can do a reduction the other way too, you get that B <= A. And if A <= B and B => A, then A and B are both in the same complexity class. If either one is NP-complete, both are.

As an example of a reduction, let's take factoring and reduce it to boolean satisfiability (SAT). In some sense this is strange because factoring is not known to be NP-complete, and and factoring < SAT ("factoring is easier than SAT") is probably strict (and so they are not in the same complexity class). But it shows the direction you have to do the reduction in, and gives a flavor of a reduction without having to explain much about the problems. We're also doing a functional variant, not a decision problem. Sue me.

Factoring is simple. Given a number n which is the product of two smaller numbers a and b, find a and b. Satisfiability is also simple. Given a boolean formula like (a and b) or (not c and a), find a way to set the variables to true or false so that the overall formula is true (or determine that is impossible). In that example, it's easy; e.g. c = false, b = false, a = true is one satisfying assignment out of many.

So how do we factor? Let's say our input number is 56. That is representable in 6 bits (111000). So we set up a 6-bit multiplication table:

Code: Select all

            a b c d e f
          * g h i j k l
          -------------
            m n o p q r
          s t u v w x
        y z A B C D
      E F G H I J
    K L M N O P
+ Q R S T U V
-----------------------
  0 0 0 0 0 1 1 1 0 0 0

(You could fill in a lot more immediately.)

How does this work? Just as you learned in 3rd grade or whatever: r = l * f, and v = k * d, and n + u + B + I + P + (carries) = 1.

Except in binary, multiplication is easy: 0 * 0 = 0, 0 * 1 = 1, 1 * 0 = 0, and 1 * 1 = 1: which looks awfully familiar if you draw a truth table. So r = l * f becomes r = l and f. Dealing with the addition is a bit harder because you have to make sure to take carries into account properly, but it can still be done. (That's why your computer can add, after all!) Finally, if you want to be a real stickler, you have to get rid of the equal signs. For r = l and f you can just replace r everywhere. For something like r = 1, you can just say r; for r = 0, you say not r.

Anyway, point being, we can translate that multiplication table into a boolean formula. And even though it'd be pretty big, the size is quadratic in the size of the input, and quadratic is polynomial so we're good.

And we can feed that formula to a SAT solver. And when it comes back and says that a = b = c = g = h = j = k = l = false and d = e = f = i = true gives a satisfying assignment, it's easy to translate that back into 7 * 8, which is the answer to our original question.

[phlip]

The idea behind NP-completeness is this "reducibility" condition, that's essentially a way of saying that a certain problem is definitely no harder than another problem.

For a familiar instance, are you familiar with logic puzzles? Specifically, this kind of logic puzzle. Take, say, the subset of those puzzles, where all of the clues are things that can be immediately written in the grid (ie no "Bob is taller than Jane" style conditions, which can't be immediately represented by ticks and crosses in the grid). You could, in theory, make a computer program that solves these - one that you give a partially-completed grid (ie one with all the clues filled in), and it tells you whether there's a solution or not.
However, this sort of puzzle is very generic, and you can often take other kinds of puzzles and turn them into logic-grid puzzles. For instance, a Sudoku puzzle can be turned into a giant logic grid puzzle, by turning the various restrictions into ticks and crosses:

A small sudoku grid

tinysudoku.png (988 Bytes) Viewed 2580 times

A logic-grid version of the same puzzle

sudokulogicgrid.png (12.3 KiB) Viewed 2580 times

The top row of the logic grid shows what number goes in which cell... the standard logic-grid deal makes sure you don't have the same number twice in a given row. The lower blocks in the grid represent "the number in cell X is the same as the number in cell Y" - the red crosses encode the "no two numbers in the same column are equal" rule, and the blue crosses encode the "no two numbers in the same block are equal" rule. The green ticks encode the given numbers in the original puzzle. You can do the same thing with a 9x9 Sudoku puzzle, it just gives you a larger grid. Writing a program to turn a sudoku into such a grid would be pretty simple, and the size of the grid you get is the square of the size of your original Sudoku grid.

So if you have a program that I mentioned before that can solve logic grid puzzles, you can use it to solve Sudoku puzzles. In a sense, Sudoku can't be harder than logic-grid puzzles - if you can solve the latter, you can solve the former. And, in particular, if you have a program that can solve logic-grid puzzles in polynomial time, you can create a program that can solve Sudoku puzzles in polynomial time, by doing this transformation.

What this means for the NP question is: say you have a problem A and a problem B, such that A can be polynomially-reduced to B (which means that any instance of A can be turned into some instance of B, which is at most polynomially as large, in at most polynomial time)... then if B can be solved in polynomial time, then so can A. Of course, there might be a way to solve A in polynomial time faster, or easier than by reducing it to B, but regardless, A can be solved in polynomial time.

NP-completeness is a property such that every other problem in NP can be reduced to this problem. The standard example (as EvanED mentioned) is boolean satisfiability. Every single NP problem can be reduced to SAT - in that, for every single problem, you can write a program which, in polynomial time, turns an instance of that problem into a boolean satisfiability question, of at most polynomial size to the original question. What this means is that if SAT can be solved in polynomial time, then every other NP problem can be too, and P=NP. Contrapositively, if P != NP, then SAT is not in P.

But SAT isn't the only such problem. In particular, there are other NP problems that SAT itself can be reduced to. Of course, this means that they can be reduced in both directions. My favourite example is Minesweeper - it's possible to encode a boolean circuit in a minesweeper grid, such that the revealed numbers are consistent if and only if the original boolean circuit is satisfiable. What this means is that Minesweeper-consistency is NP-complete too - if you find a polynomial-time solver for it, then you can use that to make a polynomial-time solver for SAT, which you can then use to make a polynomial-time solver for any other NP problem.

Also, for the record: both Sudoku and logic grid puzzles are NP-complete too. Most good puzzles are.

[EvanED]

By the way, this "completeness" and reducibility idea extends. For instance, there's a complexity class called PSPACE, which is the set of problems which can be decided using unlimited time but only polynomial space on a TM. (The space limitation bounds the time but it's EXPTIME, so ridiculously huge.)

And just like there are NP-complete problems, there are PSPACE-complete problems, and they work exactly the same. Probably the canonical PSPACE-complete problem is quantified boolean satisfiability: you're also allowed to put "there exists" and "for all" quantifiers in your formula. Any other problem in PSPACE can be solved by translating the problem instance into a quantified boolean formula and solving that. And if the other problem is PSPACE-complete, it's possible to translate any quantified boolean formula into an instance of that problem in order to get an answer for the quantified boolean satisfiability problem.

Same deal with any of the complexity classes "harder" than P and still decidable -- EXPTIME, EXPSPACE, anything in the polynomial hierarchy, etc. For classes that are easier than P (e.g. logspace) you need a more restrictive notion of reducibility (the reduction has to run in logspace instead of polytime). For classes which are undecidable (some undecidable problems are more undecidable than other undecidable problems), you use any computable reduction. But the idea remains the same: prove that problem A is no harder than problem B by showing how you can solve an instance of A by converting it to an instance of B. And if every problem in a particular complexity class is no harder than problem B, then problem B is complete for that complexity class.

(The other term you'll see is something like NP-hard. This means that the problem is at least as hard as everything in NP, but may or may not be in NP itself. For instance, quantified boolean satisfiability is NP-hard, but it is not NP-complete because it is not in NP itself. Thus we can also say that NP-complete problems are those in the intersection of NP-hard and NP; or we can say that the NP-hard problems are the union of NP-complete problems and those which are strictly harder than NP (and thus not in NP). And like the above, this extends to other classes, like PSPACE-hard.)

[Joeldi]

Thanks so much, that definitely helped with reduction/transformation, which is definitely what the others places I looked didn't explain very well. And it solidifies my understanding of NP-Hard. So is the idea that the inputs parameters of an x-Complete problem can be f'nagled to accept input from any x problem? But P ?= NP says we don't know for sure if there are any NP problems that definitely can't be f'nagled into NP-Cs, but they probably do exist? If I'm following, can you give an example of an NP problem that's hard to f'nagle, but with no obvious reason that it can't be?

EDIT: Sorry, haven't had a chance to read Phlip's explanation yet. It may have answered that question.

[phlip]

Well... that's an interesting question. In particular, the definition of NP-complete becomes kinda useless if P=NP, as every non-trivial problem (ie has some instances where the answer is "YES" and some where the answer is "NO") in P would then be NP-complete. Because if you can solve every NP problem in polynomial time, then you can just solve the problem in the "reduction" step, since that can take polynomial time.

But assuming P!=NP, then we can certainly show that there are problems that aren't NP-complete... anything in P, for instance (since any NP-complete problem in P immediately implies P=NP). And then there's things like integer factorisation, which is in NP, and usually assumed (though unproven) to be in neither P nor NP-complete. I don't know offhand of any problems that are assumed to be NP-complete but this hasn't been proven yet... they probably exist, though.

[Proginoskes]

Well... that's an interesting question. In particular, the definition of NP-complete becomes kinda useless if P=NP, as every non-trivial problem (ie has some instances where the answer is "YES" and some where the answer is "NO") in P would then be NP-complete. Because if you can solve every NP problem in polynomial time, then you can just solve the problem in the "reduction" step, since that can take polynomial time.

It isn't useless now, though.

But assuming P!=NP, then we can certainly show that there are problems that aren't NP-complete... anything in P, for instance (since any NP-complete problem in P immediately implies P=NP). And then there's things like integer factorisation, which is in NP, and usually assumed (though unproven) to be in neither P nor NP-complete. I don't know offhand of any problems that are assumed to be NP-complete but this hasn't been proven yet... they probably exist, though.

Graph Isomorphism hasn't been shown to be NP-complete yet.

[phlip]

It isn't useless now, though.

Right... my point is, that as long as P!=NP hasn't been proven, we can't prove that any non-trival NP problems aren't NP-complete, which was part of the question.

Graph Isomorphism hasn't been shown to be NP-complete yet.

Neat! Thanks.

[Yakk]

Thanks so much, that definitely helped with reduction/transformation, which is definitely what the others places I looked didn't explain very well. And it solidifies my understanding of NP-Hard. So is the idea that the inputs parameters of an x-Complete problem can be f'nagled to accept input from any x problem? But P ?= NP says we don't know for sure if there are any NP problems that definitely can't be f'nagled into NP-Cs, but they probably do exist? If I'm following, can you give an example of an NP problem that's hard to f'nagle, but with no obvious reason that it can't be?

I think the previous two posters answered an interesting question, but it wasn't the question you asked.

If we can prove that something is in NP, then we can f'nagle it to turn it into an NP-C problem, as far as I know. (Possible holes in my knowledge: the existence of the reduction -- ie, the proof that the problem is in NP -- might be non-constructive. Alternatively, there might be ways to show something is in NP without reducing it to an NP-C problem)

There are problems that we do not know if they are in NP or not. The computational hierarchy is full of this problem -- we have chains where LSPACE <= P <= NP <= PSPACE, and we know that PSPACE != LSPACE, so we know that one of the inequalities is not an equality, we just do not know which one. (I chose sufficiently far apart spaces that don't equal each other -- I think the point where we don't know they equal is a small amount closer). In a vague sense, for most complexity classes and most problems, we don't know if that problem is in that complexity class or not!

I believe there are some really restrictive spaces which we know contain problems that are strictly weaker than NP-C problems. I don't know the name of such a space off hand, but I could try to look it up in wikipedia -- their complexity theory pages are pretty comprehensive.

The way NP is defined, however, means that being able to be P-time reduced to an NP-C problem is equivalent to being in NP.

There are many ways to define NP. My favorite is "problems whose answer can be proven, if only you could find the proof. The proof must be short (polynomial in length of the problem) and easy to check (polynomial in length of the proof)." The NDTM interpretation can then be looked at as searching the entire proof space, where the "successful" accepting run's "choices" encode the proof. A DTM could use that sequence of "choices" to confirm the answer the NDTM claimed to be true. Any answer with the attached proof is going to be accepted, so you can determine if the proof is a lie.

You can view NP-complete problems are problems that are strong enough to do general proof checking in a logic system strong enough to model Turing Machines with at most polynomial time overhead.

Then P=?NP becomes the question "Is the existence of a short proof for the answer to a question equivalent to it being easy to find the proof?" Which sort of explains why many people think it is not true.

Was that at all clarifying?

[EvanED]

The computational hierarchy is full of this problem -- we have chains where LSPACE <= P <= NP <= PSPACE, and we know that PSPACE != LSPACE, so we know that one of the inequalities is not an equality, we just do not know which one.

Stephen Cook gave a talk at my school a few years ago about NP. (He's one of the people who formalized the idea of ptime reductions and NP-completeness and such.) There was one part that stuck with me, because it was amusing, and it concerns that. He was explaining why theorists think that P != NP, and he said something like

"Why? Well, the algorithms people seem to be really good at coming up with algorithms for problems, and they have yet to come up with a PTIME algorithm for any NP-complete problem. Meanwhile, us complexity theorists seem to be really bad at proving distinctions between complexity classes. Here, i'll prove it: [puts up L <= P <= NP <= PSPACE]. We know that one of those inclusions is strict, but not which one!

There are many ways to define NP. My favorite is "problems whose answer can be proven, if only you could find the proof. The proof must be short (polynomial in length of the problem) and easy to check (polynomial in length of the proof)."

My impression is that in practice this is by far the easiest definition to work with for most problems. Note though that Yakk's definition is a little imprecise: only positive ("yes") instances need proofs. (Typically these "proofs" are called "certificates".)

For instance, with boolean satisfiability (SAT), the yes/no question is "can you assign the variables so that this formula is true?", and if it is possible to do so, the proof is just the variable assignment. That assignment is smaller than the original formula, and if I give it to you it's easy to see if it works -- just plug and chug. (By contrast, it's much harder to prove that an unsatisfiable instance isn't satisfiable: but this isn't required by the certificate definition of NP.)

[Proginoskes]

"Meanwhile, us complexity theorists seem to be really bad at proving distinctions between complexity classes. Here, i'll prove it: [puts up L <= P <= NP <= PSPACE]. We know that one of those inclusions is strict, but not which one!

This is because L < PSPACE is provable, and the rest are obvious. (I debated putting quote marks around 'obvious' but decided that it really is obvious.)

The problem in resolving these issues is that there seems to be only one technique for proving that two complexity classes are distinct, and it's a severely limited one. (Diagonalization.)

[tomtom2357]

After PSPACE there is EXPTIME, NEXPTIME and EXPSPACE, so we have an inequality L<=P<=NP<=PSPACE<=EXPTIME<=NEXPTIME<=EXPSPACE and we have L<PSPACE<EXPSPACE, P<EXPTIME, NP<NEXPTIME, and EXPTIME=NEXPTIME if P=NP. We also have PSPACE=NPSPACE, which shows that X can be equal to NX.

[philoctetes]

Oh, well, while we're listing them... While we don't know where BPP or BQP stand in relation to P and NP, we know that BPP <= BQP. Connecting randomization in some sense, though, we also know IP = PSPACE, and also QIP = PSPACE from which we get QIP = IP.

[tomtom2357]

Oh, well, while we're listing them... While we don't know where BPP or BQP stand in relation to P and NP, we know that BPP <= BQP. Connecting randomization in some sense, though, we also know IP = PSPACE, and also QIP = PSPACE from which we get QIP = IP.

Yes, you could list those, but those involve randomness or quantum processes.I would prefer to stick with deterministic algorithms that don't rely on possible quantum computers that might not work in reality.

[Yakk]

BQP does not 'rely' on quantum processes, no more than NP 'relies' on having a physical NDTM. It is a formal complexity class inspired by QM based computation, that we are relatively sure can be realized in theory by a sufficiently complex arrangement of atoms in our reality. But it does not rely on that.

Anyhow, the braid based QM computers that are being talked about sound interesting. God damn experimentalists, taking a nice abstract branch of mathematics and threatening to make it practical.