Hacker News Reader

Comment by mathewsanders | Hacker News Reader

I’ve tried a few times to understand what P=NP means and never felt like I understand what it’s about.

I get that problems can have constant/linear/polynomial/exponential complexity to solve so I (think) I understand ‘P’.

Over at NP I get confused around what constitutes a test/validating that a solution is true in polynomial time.

For example, a problem, “what’s the shortest path between two points” I get that a brute force breadth-depth first algorithm is going to rapidly take longer as more branches are added, but what constitutes verifying the solution?

In that example does verifying a solution mean having access to some prior list of all possible permutations and sorting them to find the shortest path, and because sorting is easy then this is an example of easily verifying?

View on HN

There's a lot of handwaving in practice over complexity classes. Strictly speaking, P and NP only consist of decision problems, that is, the expected output is solely "YES" or "NO". In practice, however, we mostly care about functional problems, ones that give a result. Your example of "what's the shortest path between two points" is such an example: the decision variant is "is there a path between two points less than k?"

The general process to convert a function problem of "find the best X for this input" to a decision problem is to recast it as "is there an X better than k for this input?" So the validation in these cases means finding that a) the claimed X is actually an X on the input (e.g., a sequence of nodes to visit is actually a valid path in the first place), and b) you can measure the property of X you're trying to optimize (e.g., what is the total cost of the path).

Another way to think of it--one which actually illuminates the underlying proofs a bit better--is that NP is a nondeterministic class. Basically, this means that any problem in NP [in the fuzzy sense] can be thought of as a polynomial-time algorithm, but every time we have to make a "choice" of some kind (which node to pick next, which color to assign it, etc.), we can ask a magic oracle which tells us the correct answer in O(1) time.

and NP only cares about being able to verify YES answers. co-NP cares about verifying NO answers. It's unknown whether or not NP and co-NP are equal.

> Your example of "what's the shortest path between two points" is such an example: the decision variant is "is there a path between two points less than k?"

Just to add to this: This can obviously also be brought back to "find the shortest path", by just asking the question again and again for smaller and smaller k, by halving.

NP are the problems which we can verify an answer to 'quickly'.

P are the problems that we can create an answer to 'quickly'.

The question is, if we are able to verify an answer quickly, does that imply we can also always create an answer quickly? It feels like obvious not the case, but we can't prove it either way.

One fun fact is that Sudoku (on a n by n grid) is NP-complete.

It's in NP because given a sudoku problem instance (a n by n grid with only some clues filled in) and a proposed solution (a n by n grid with all the squares filled in) you can check if the solution is correct in polynomial time. That is, you check that each square in the problem is equal to the square in the solution, and you check the rows/columns/larger-squares to see if they each contain the values (1..n).

So a problem X is in NP if given a polynomial-sized certificate C, you can run a polynomial-time algorithm C_Check() to see if it is actually a valid solution. In the sudoku problem:

X is Sudoku with instance x C is the proposed solved sudoku C_Check(x, C) is the algorithm where you check the rows/columns/larger-squares and you check that for every square in X[i][j] that is filled, C[i][j] == X[i][j]

In a normal breadth first search, where there are a polynomial # of vertices, you actually don't even need to use C until the very end. You're allowed to say

X is ShortestPathProblem with instance x C is the proposed shortest path C_Check(x, C) is just (BFS(x) == C)

So therefore any problem in P is automatically in NP.

If you are genuinely interested in understanding this, I would be interested in helping you get there. I'm not an expert, but when I've spoken with people who are experts, they have told me that I'm getting things right.

An email address that works for me is in my profile.

Strictly speaking, NP problems need to have boolean outcome, so "what's the shortest path" is not an NP problem. Instead, "is there a path with cost <= X?" is an NP problem.

Of course, if I had a polynomial-time solver for the "cost <= X?" query, I could easily create a polynomial time solver for the cost of the shortest path, using binary search.

See Decision Problem: https://en.wikipedia.org/wiki/Decision_problem

> For example, a problem, “what’s the shortest path between two points”

Switching to the decision version: "Is there a path of length at most L between the two points?"

To verify a "yes" answer, you get a path; and you just verify that it's short enough and goes from the first point to the second; that's it.

Obviously this verification doesn't work for a "no" answer.

To verify the shortest path, you would need to compute all the other paths as well, to be sure. so this doesn't sound like NP-complete

This confusion is caused by the different notions of problem: there are "decision" problems and "functional" problems. What grandparent asked ("what is the shortest path?") is a functional problem in nature, whereas P & NP are classes of decision problems. A (more or less) equivalent decision problem version of above question would be "is there a path of length at most X?", which then is of course easy to verify if a potential solution is presented.

Reply on news.ycombinator.com