What are NP and NP-complete problems? [closed]

Question

I am struggling to understand what are nondeterministic polynomial-time problems and NP-complete problems. I understand what polynomial-time solvable problems are, and saw in Wikipedia about NP problems. After reading about this I tried to think about some example problems. As I understand it, depth-first search in an undirected is NP-complete, since each decisions can be made nondeterministically (i.e if I made the wrong decision, I could instead try some other choice) if the graph is large (cit an be polynomial if graph size is small.)

Can anyone briefly explain all these NP terms with simple examples without using much maths?

Answer 1

There are many ways of thinking about NP and NP-completeness. I'll start with a definition of NP, then will talk about NP-hardness, and finally NP-completeness.

At a high level, P and NP are classes of problems. A problem is in P if is a yes-or-no question (a decision problem) and there is some algorithm that solves the problem in polynomial time. For example, the question of "can you get from node u to node v in this graph?" belongs to P because you can solve it with depth-first search. (Note that DFS itself is not in P, since DFS is an algorithm rather than a problem). Another example of a problem in P would be checking whether a sequence is in sorted order.

A problem is in NP if it is a yes-or-no question (a decision problem) where a correct answer can be verified in polynomial time. For example, a classic NP problem is seeing whether, given a set of weights of known weight, you can pick a set of weights that weighs exactly some amount k (this is called the subset sum problem). It might be tricky to figure out whether a set of weights with that property exists, but if I were to give you a set of weights that I said I knew was correct, you could very easily check whether or not I had given you the correct set of weights by just adding them up and seeing if they totaled k.

The reason that NP is called "nondeterministic polynomial" is that a different way of thinking about NP is to think about a magic algorithm that can somehow guess the correct answer to a problem in polynomial time. That is, if you can write an algorithm that is allowed to make guesses about the answer to a problem and runs in polynomial time, then the problem you are solving is in NP. To go back to our weights example, we could write such a guessing algorithm for the problem as follows. Start off by, in linear time, guessing which set of weights is the correct set of weights, then add them all up and see if they total k. If so, report that the answer is "yes." Otherwise, say "no." If this program is always guaranteed to make correct guesses, then given any input to the problem that has a solution it will always find one and report "yes," and if there is no solution it will always guess wrong and report "no."

One of the most fundamental and important questions in computer science right now is whether any problem that is known to be in NP is also in P. That is, if we can easily verify the answer to a problem efficiently (in polynomial time), can we always solve that problem efficiently (in polynomial time)? It is known that any problem in P is also a problem in NP, since you can use the polynomial time algorithm to produce an answer and then check whether it's correct, but no one has ever found a way to solve arbitrary problems in NP in polynomial time.

The reason for this is that some problems in NP are known as NP-complete, meaning that (informally) they are at least as hard as every other problem in NP. If we could solve these problems efficiently (polynomial time), then we could solve every problem in NP in polynomial time. This would be a huge deal, since there are a lot of problems in NP that are extremely important that we currently have no good, fast algorithms for. This is also the allure of the P = NP question, since all it would take would be one algorithm to show that an enormous class of problems presumed to be impractically hard to solve would actually be solvable efficiently.

More formally, a problem in NP is called NP-complete if, in polynomial time, you can transform any instance of any other NP problem into an instance of that problem. The above problem with weights is such a problem, as is the problem of determining whether a boolean formula has a satisfying assignment, solving certain optimization problems over the integers (integer programming), determining the fastest route to visit a set of locations (traveling salesman), or determining how to assign cell towers in a city using the smallest number of frequencies (graph coloring). Even determining whether it's possible to solve a game like Sudoku and minesweeper are known to be NP-complete for arbitrary board sizes.

(Some problems have this latter property - that any problem in NP can be converted efficiently into that problem - but aren't themselves in NP. Those problems are called NP-hard.)

From a practical perspective, if you are ever asked to solve a problem that is known to be NP-complete or NP-hard, don't expect to find an exact solution in any reasonable time. In some cases, it's not even possible to approximate solutions to within any precision efficiently. You are best off looking for an alternative problem to try to solve or to resign yourself to a heuristic solution that does well in most but not all cases.

As to your original thoughts about DFS being NP-complete, only problems can be in NP or be NP-complete; algorithms cannot. DFS is an algorithm for solving the graph reachability problem - given two nodes in a graph, is there a path from the first to the second? That problem is in NP because if there is a path it's easy to check, but it's (probably) not NP-complete because we know we can solve it in polynomial time using DFS.

Hope this helps!