P vs NP for non-mathematicians

Factual Questions
1

Been reading up on P vs NP a bit, and I’m trying to grasp it. For those who do grasp it, can you please answer my question at the bottom of this post, which relates to 3 examples listed below:

1. Which number is the highest?
Let’s say you give someone an unordered list of random numbers. You ask them to tell you which is the highest number from the list. They come back to you and say “93 is the highest number from this list”. Verifying whether the proposed answer is correct takes about as much time as solving it in the first place.

  1. Place 8 non-threatened Queens on a chessboard
    Give someone a chessboard and 8 Queens. Ask them to place all 8 Queens on the board so that no Queen threatens any other Queen. Verifying whether a proposed solution is correct is much faster than figuring out how to complete the given task in the first place.

  2. The travelling salesman
    Select a random US State, and from it, select 20 random cities. Assuming it is possible to fly in a straight line from any city to any other city, figure out the shortest possible route/distance you must travel to visit every city at least once. It is very difficult to verify whether a proposed solution is correct, and it is very difficult to determine what the shortest possible route is.

Can someone please assist me by explaining which of the above is an example of the “P vs NP” problem, and, what would a theoretical solution to P vs P enable me to do, if I found myself in any of the examples above?

Please note: I ask that all answers be written in such a manner that they are comprehensible to non-mathematicians. It would really help if you could fit any answer/explanation in to an easy-to-grasp example, like hopefully, my ones above are :slight_smile:

Thanks!

2

This is purely from the PoV of an intelligent layman.

Only in your case #2 can the answer be verified quickly, so it’s the only one covered by this clause, and in its case you have stated the answer cannot be computed quickly.

3

“Polynomial time” means that the difficulty grows no more quickly than some power of the size of the input. P-time means that the problem can be solved in polynomial time. NP (which stands for non-deterministic polynomial) means that a solution can be verified in P-time, but may not found. If you have an oracle (that’s the non-deterministic part) that suggests a solution, you can verify it in P-time. The 8 queens problem is clearly NP, but note that NP does not preclude P. Another, obviously NP problem is finding prime factorizations of numbers. You could verify a proposed solution quickly (even by hand of a 1000 digit number is an afternoon) but finding a factorization in the first place is thought to be hard. Now I have read, although I find it hard to believe, that the traveling salesman problem is also NP.

Then there are the NP-complete problems of which the traveling salesman problem is one. Should any NP-complete problem have a P-time solution, they all will. The factorization problem is not (or not known to be, I am not clear on this point) NP-complete. So the P vs. NP question is really the question whether any NP-complete problem has a P-time solution and is the biggest unsolved problem in computer science. Note that the security of most common trapdoor cipher depends on factorization being not P-time.

4

Note that the general form of 8-queens (n-queens on an nxn board) is not known or suspected to be hard. (As in NP-Complete or a related difficult class.) So an easy solution might be found without impacting the P vs. NP question.

In general, please avoid clear-cut statments like saying a problem in NP is “very difficult” as we simply don’t know this. Throw in qualifiers like “suspected to be difficult” or even better “is NP-complete” (or “NP-hard”).

So the OP’s first 2 examples have nothing to do with P vs. NP.

The third example, Travelling Salesperson (if it were correctly stated, sigh), does. It is NP-hard. And that’s basically due to not being a yes-no question. The yes-no version would be “Is there a route of length of at most X?” which is NP-complete. Note that given such a route, verifying that all cities are visited once and the total is at most X is easy. (It’s the visiting each city once part that makes this a non-trivial problem. The cost part is just noise.) Note that the yes-no version can’t be a significantly easier problem than the optimization version as one can use any solution to the yes-no version to find an optimal version in a binary-search style method. Costs just a polynomial factor more.

5

Doesn’t this need tempering, a bit? If factorisation was definitely in P, but all known algorithms had absolutely gargantuan exponents, then our cyphers are still safe, no? In fact, it still needs tempering, as it’s possible to prove non-constructively that factorisation is P-time without being able to come up with a polytime algorithm for it, no?

Factorisation is in co-NP, so probably isn’t NP-complete.

6

Polynomial time - means that the formula to find the answer is dependent on a polynomial of the number of inputs. Yes, this is very simplified - the usual factor that the polynomial depends on is number of inputs.

For example - sort X items. The most basic sort is the “bubble sort”.
It’s like taking some cards or folders or whatever and inserting into a drawer in ascending order.
Put the first in.
For each one after that, start at the first, leaf through until you find the place it belongs, insert. If there are I cards in the drawer already, on average, that takes I/2 checks.
I runs from 2 to X; so to sort X items, it takes (X)(I/2) operations (read, compare) on average.

For example, the 57th card - start at 1; goes before?No. card 2 - goes before it? No. and so on to let’s say, card 35. Goes before it? Yes (and obviously, after card 34.) Put card in its proper place.

I runs from 2 to X, so about X/2 iterations. So the bubble sort takes about (X)(X/4) or (X^2)/4 operations. If we double the number of items to sort - 2X then the time taken is 4(X^2)/4 operations. The time to do the problem is polynomial in X, the inputs. It’s a poynominal in X squared.
(There are cleverer algorithms, that get it down to X log X or better.)

That sounds like a lot - double the inputs, quadruple the time. However, consider the travelling salesman problem - visit X cities at lowest cost. The number of possible paths is the number of possible combinations of the X cities in order - or roughly Factorial X. The simplest algorithm is to check them all, every possible combination. Double the number of cities and the number of connections does not go up by a factor of 4, or 8, or 9 - it goes up by a number like A^X

The exponent of the expression of how long/how many operations to determine the solution is not a fixed number (2, or 3, or 4, or whatever) but the X of the inputs. The cost to perform this task grows at GREATER than polynomial value, so it is an NP problem.

You can make a heuristic solution quickly - a good guess, so to speak - start with the lowest cost path, then the next one, etc. But to prove that there is no cheaper route? That is still NP.

It’s been 25 years since I did NP-P stuff, but that is the essence of the problem. It was esoteric stuff at the time, but think about something like Google - how do you find the websites that fit your query without searching every one, or having a huge huge huge index of words? What good is a sorted index if we are looking for partial words? Etc.

7

No it doesn’t!

8

Not known to be. You have to really work to come up with an example of a problem that is known not to be NP-complete (in particular, the only ones that I can think of are those that are complete for NEXPTIME or some higher nondeterministic time class).

OP, remember that the defining characteristic of NP is that, for any problem in it, a proposed solution can be verified in polynomial time, not just quickly. That polynomial is a function of the problem size, not the number of inputs.

9

[nitpick]You’ve described insertion sort.[/nitpick]

10

This can be just a restatement of the same thing, if, for instance, you consider a large number to be a sequence of bits, and call each bit an input.

11

For numerical problems, that’s the usual definition of input size, but it’s not the only notion. For something where you’re operating on a list of numbers, you usually measure the problem size by the length of the list.

12

Though for the specific problem P vs. NP, it is vital that the definition of input size be (essentially equivalent to the one) in terms of the number of bits to specify the input.

Anyway, for the OP: most pop-mathematical explanations of P vs. NP are really explanations of FP vs. FNP. That’s alright; P = NP if and only if FP = FNP (and is equivalent to a million other more and less interesting things as well). But it does tend to confuse the introductory discussions to not keep the notions clear and distinct. Let’s try and spell out what they all amount to:

A predicate (also called a relation) is any sort of yes/no question you might ask with various input slots; e.g. “Is N a prime number”, “Is the number X a nontrivial factor of the number Y”, “Is there a path in the graph G of length D with starting node X and ending node Y”, and so on.

Notation: In general, we use notation like “R(X, Y)” to introduce a relation named R with input slots named X and Y, and then write “R(thing1, thing2)” to mean either YES or NO, according as to the answer to the question R when thing1 is substituted in the X slot and thing2 is substituted in the Y slot. [And similarly for relations with any number of input slots]. If we want to refer to the relation itself, we can use either “R” or “R(X, Y)”, depending on whether we want to emphasize the input slots or not. [This is all just notation, but it makes life easier]

A binary relation is just a relation with two input slots. Let’s suppose we’re interested in a binary relation R(X, Y). There are various associated computational tasks we can ask about.

For example, we might consider the problem “Given X and Y as input, output the yes/no value of R(X, Y)”. This is what we might call the check-problem (or verify-problem) associated with R. R is said to be in FNP if there is a computer program which does this, whose running time is running time (measured by number of computational steps) is never more than some fixed polynomial of the size of the input X alone (measured by number of bits to specify X alone).

Or, we might consider the problem “Given an X as input, either output a particular Y such that R(X, Y) = YES or output an error code indicating that there is no such Y”. This is what we might call the search-problem associated with R. R is said to be in FP if A) there is a computer program which does this, whose running time is never more than some fixed polynomial of the size of the input X, and B) R is also in FNP.

By definition, every binary relation in FP is also in FNP. However, it’s not known whether the converses hold; that is, it’s not known if condition A) above is redundant. That’s the big question.

What about P and NP?

A predicate Q(X) with just one input slot is said to be in NP if there’s some R(X, Y) in FNP such that the answer to Q(X) is always the same as the answer to the question “Does there exist a Y such that R(X, Y) = YES?”. (Note that there may be more than one such R; as long as there’s any way to cast Q into this form, then Q is in NP)

Finally, a predicate Q(X) with just one input slot is said to be in P if there is a computer program which, given an input X, will output the yes/no answer to Q(X) in a running time bounded by some polynomial of X’s size.

It’s easy to see that every predicate in P is also in NP. However, it’s not known whether the converse holds. That’s the big question. In fact, as I said at the top, it’s the same big question from before; it’s fairly easy to show that P = NP if and only if FP = FNP.

How does any of this apply to the problems in the OP? Well, I’ll put that in the next post.

13

Which number is the highest: Consider the binary relation “Y is the highest number in the list X”. This is in both FNP and FP; the associated verification- and search-problems can both be carried out very quickly, in time polynomial in X.

Place 8 queens on the chessboard: this question has too few input slots, as stated, so it’s not the right sort of thing for this framework. However, generalizing the 8, as mentioned above, we might consider the binary relation “Y is a configuration of X many queens on an X by X chessboard with none attacking each other”. This is clearly in FNP, as the associated verification-problem can be carried out very quickly, in time polynomial in X. However, it’s not obvious whether or not this is in FP. I don’t know of any fast way to carry out the associated search-problem, but I don’t know of any proof that there is no fast way, either. Anyway, because this binary relation is in FNP, the related unary predicate “Is it possible to put X queens on an X by X chessboard with none attacking each other?” is, by definition, in NP. I don’t actually know anything about the n queens problem, but I suspect it’s always possible beyond a certain size? In that case, this unary predicate would, of course, be extremely easy to calculate, and be in P as well.

Finally,
The travelling salesman problem: The binary relation “Is Y a path through the graph G with length less than D (where X is considered to be the combined information of G and D)” is of course in FNP (easy to check, in time polynomial in X; note that part of making this easy to check was including the desired distance D as part of X). However, it is not known to be in FP; in fact, it is very strongly suspected not to be in FP. I’ll come back to this in a second. Therefore, the associated unary relation “Is there any path through the graph G with length less than D (where, again, we can take the single input X to be the combined information of G and D)” is, by definition, in NP. However, it is not known to be in P, and, in fact, it has been proven that if any problems in NP aren’t in P, then this is one of them.

14

Long cat is long. The underlined words are of course an editing error and should be removed.

15

The usual factor. In all the examples we were given in class on NP vs P, the general number that the time to evaluate formula was tied to was input. (As in “sort X items” or “travel to X cities”). If this is not the usual (not 'the only") way to formulate this problem, I’m all ears to hear some other examples. Factoring a very large number, the X is probably the number of digits or the value of the number.

Of course, it’s been over 25 years so I’m a bit fuzzy on the details, but the teacher - Cook’s Theorem Cook - was pretty good, and obviously knew his stuff.

16

As mentioned above, for the purposes of P vs. NP, polynomial time means polynomially bounded in the number of bits to specify the input. In many examples, this is equivalent to being polynomially bounded in the “number of items”, suitably construed, but the former description is a bit more concrete. (Yes, for problems whose input is a single number, this is equivalent to being polynomially bounded in the the number of digits)