P ≠ NP (part 2 correction)

In the previous post I said that one example of an NP problem is “Check if two computer programs always produce the same output.” jkff commented:

The "check if two computer programs always produce the same output" is not NP. It's simply undecidable and cannot be solved in any amount of time.

I blew it and oversimplified the statement. At Wikipedia, they have a list of commonly known NP-complete problems and on that list is “Inequivalence of simple functions.” I seriously mangled the meaning because I was daydreaming about assembly code. What I should have done is put some restrictions on what sort of computer program I meant.

First, we have to restrict ourselves to programs that we can prove will always return an answer within a given amount of time. A computer program that does not have any loops, backward jumps (gotos), subroutine calls, or exceptions should simply run from from start to finish. Second, we do not allow the program to save any state between runs; the output must be a pure function of the input. Furthermore, we restrict the input to a finite set (for example, integers that expressible in a single 32-bit word). Now suppose we have two such programs. To prove they are not equivalent, we need to find a 32-bit integer input that makes each program give a different answer. By trial and error we will eventually find such an input or exhaustively show that there is none. However, if someone were to claim that a particular input produced different output, then it is easy to check by simply trying it out.

P ≠ NP (part 2)

As I mentioned in my last post, P and NP are commonly encountered complexity classes. Knowing what complexity class a problem is in can give us some idea of how difficult it may be to solve the problem. So what's the difference between P and NP? I don't want to get into the technical definition of P and NP, so I'm going to make broad generalizations that aren't technically rigorous, but will give you a feel for the difference.

Problems in class P are generally considered “tractable” by computer scientists. By this we mean that a computer can probably solve such a problem efficiently and relatively quickly. Recall that the complexity classes relate the ‘number of pieces’ to the difficulty. If you can solve a particular problem in P, then a similiar problem with a ‘larger number of pieces’ is likely within your grasp (and if not, it is usually a question of upgrading to a better computer). Problems in class P are the ‘meat and potatoes’ of computer programs.

Before I discuss NP, let me introduce the complexity class EXPTIME. EXPTIME is where you find some really hard problems, like computer chess or Go. It is true that there are computers that can play chess really well, but if we were to modify the rules of chess to add a couple of new pieces and make the board 9x9 instead of 8x8, it would greatly increase the difficulty of the game. Problems in EXPTIME are generally considered “intractable”. By this we mean that a computer will have a hard time solving such a problem efficiently and quickly. And if you are able to solve a particular problem in EXPTIME, then a similar problem with just ‘a few more pieces’ is likely beyond your grasp, no matter how fancy a computer you might buy. Problems in class EXPTIME take a lot of time and money to solve.

So what about NP? Problems in NP are quite curious. They seem to be very difficult to solve, much like EXPTIME problems, but they have the unusual property that it is very easy to check if a solution is correct. Let me illustrate: if I showed you a chess position and claimed that it was a good position for white, you'd have to do a lot of work to verify whether my claim was true. In fact, it would have to be about the same amount of work it took me to come up with the position in the first place. On the other hand, if I were to show you a jigsaw puzzle and claim that I had finished it, you could tell at a glance whether my claim were true. Problems in NP seem to be much harder to solve than problems in P, but as easy to verify as problems in P. That is a little weird.

Problems in NP are often encountered in computer programs, and many of these kind of problems, although very difficult to solve, have approximations that are relatively easy. In some cases, when a perfect solution is not needed, one that is ‘good enough’ will be a lot easier to compute. Another weird thing is that a lot of problems in NP don't sound at all like they'd be hard to solve. Here are some examples:

• Take a group of people and divide them into two subgroups such that both subgroups have exactly the same amount of change in their pockets. (No, you aren't allowed to move the change around.)
• Find the shortest path that visits all the major landmarks in a city.
• Check if two computer programs always produce the same output.  Whoops!  I blew this one.  Check the next posting.

There is one final bit of weirdness. It is easy to prove that EXPTIME problems are much harder to solve that P problems, but no one has proven that NP problems are harder than P problems. (or that they aren't harder than P problems!) This isn't for lack of trying. Many smart people have worked on a proof for some time. There's a million dollar prize for the first person to prove this one way or the other. Recently, Vinay Deolalikar of HP Labs claimed that he has a proof. Unfortunately, other experts in the field have pointed out flaws in the proof that may invalidate it.

P ≠ NP (part 1)

I'm sure most people who read this blog know a bit about what this means, but I want to try to explain it in a way my mom could understand. I won't go into excruciating detail, and I'll probably gloss over interesting points.

Let's start with an analogy. Suppose you go to the store to buy a present for your nephew. He likes jigsaw puzzles, so you want to get him one. He's going to be twelve years old, so you need to find one that has the appropriate challenge. A simple one with four pieces might be great for a two year-old, but your nephew would find that boring. A big one with ten thousand pieces is probably too much for him. You know he just finished one with five hundred pieces, so you pick one with six hundred pieces because it won't be too easy, but not too frustrating. What you are doing is estimating the complexity of the puzzle.

When you get to the store you find that they are sold out of jigsaw puzzles. They have a variety of other puzzles, though. They have a Rubik's cube, a Sudoku book, some cryptograms, a Tower of Hanoi, etc. They have models you can put together as well. But these things aren't jigsaw puzzles. You can't estimate the complexity the same way. A model with five hundred pieces would be quite a bit more difficult to assemble than a jigsaw puzzle with the same number of pieces.

Perhaps you look at the age ratings for the various puzzles. The eight-piece Tower of Hanoi puzzle is rated for ages ten and up, so maybe a twelve piece? The standard 3x3x3 Rubik's cube is rated for ages eight and up, but would the 4x4x4 be too hard or too easy? What about the 5x5x5?

The kind of rating system you use to describe the difficulty of a puzzle is analogous to the “complexity class” of a problem. The complexity class roughly describes how hard a problem will be to solve, and more importantly, how much harder ‘big’ problems are compared to the ‘small’ ones. Here's what I mean: if I take a jigsaw puzzle, any jigsaw puzzle, and double the number of pieces in it, I'll make it roughly twice as hard (more or less). If I take a cryptogram and double the number of words in it, I'll actually make it a lot easier. If I take the Tower of Hanoi and double the number of discs, I'll make it incredibly harder, maybe even impossible. These puzzles are in different complexity classes.

As it turns out, a lot of puzzles are in the same complexity class as the jigsaw puzzle: the difficulty is reasonably proportional to the number of pieces. Adding a piece or two doesn't change things that much, and it is easy to figure out how long it will take to solve if you've done a few of them. A lot of puzzles are more like the Tower of Hanoi. Adding a single piece will double the amount of time it takes to solve them.

P and NP are complexity classes for problems you might want to solve on a computer. There are all sorts of rating systems, but everyone is familiar with the MPAA movie ratings. There are all sorts of complexity classes, but most computer scientists are familiar with P and NP.

I'll pause here because the analogy is wearing thin. The main point is that “P ≠ NP” is a statement about complexity classes. In particular, it talks about two of the most popular complexity classes and that is part of the reason it is interesting.

Rambling

Writing a blog is hard. I need practice so I'm going to ramble a bit.

First, I'm very pleased that Blogger has improved their comment spam detection. Every time I made a post I'd have to come back a day or two later and remove a bunch of pointless comment spam.

Second, I told my daughter that someone claims to have a proof that P ≠ NP. She replied “Well, now we know that N doesn't equal 1.”

I read through the proof and I confess that I don't get it. On the other hand, I think I want to get it, so I'll have to learn some interesting things.

Here's another thing I don't get.

`` E8 is any of several closely related exceptional simple Lie groups and Lie algebras of dimension 248''

``a simple Lie group is a connected non-abelian Lie group G which does not have nontrivial connected normal subgroups.''

``a Lie group is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure.''

``a non-abelian group is a group (G, * ) in which there are at least two elements a and b of G such that a * b ≠ b * a.''

``a connected space is a topological space which cannot be represented as the union of two or more disjoint nonempty open subsets''

Happy 80th Birthday to Neil Armstrong

Neil Armstrong turns 80 years old today!

My definition

Here's my definition:

A computer program is a description of a process which is formal enough to be carried out by a machine.

Most of the other definitions describe a program as a ‘set of instructions’. Some of the definitions suggest that these instructions should be organized in some way, perhaps as a (linear) list. These instructions ‘make the computer do things’, ‘bring about a certain result’, ‘cause the computer to behave in a predetermined manner’, or ‘alter the contents of memory’. But these definitions have an explicit or implicit assumption: a sequential, imperative mode of thought.

Look at this Prolog code:

append(c(H,T), B, c(H,TB)) <= append(T, B, TB).
append(nil, B, B).

This code describes relationship of appending lists, but it doesn't specify how to accomplish the appending. Is the first clause an ‘instruction’ to build a list, or to take one apart? Are the clauses to be run in any particular order? Is there a deterministic ‘answer’?

What is a ‘computer program’?

This seems like a simple enough question.

Here's what the web says. A computer program is

1. a set of statements or instructions to be used directly or indirectly in a computer in order to bring about a certain result
2. what makes the computer do things
3. a set of instructions written in a programming language
4. an algorithm written in a language that a computer can understand
5. simply a long list of code written in another language
6. a set of instructions for altering the contents of various words in the computer's memory
7. a carefully thought out, step-by-step, set of instructions prepared by a programmer
8. an organized list of instructions that, when executed, causes the computer to behave in a predetermined manner
9. is a procedure (or algorithm) for performing some computation
10. a bunch of instructions run by a computer, just like a storybook is just a whole bunch of sentences read by the reader

Does anyone have any better definitions?