What is the difference between solving and verifying an algorithm in the context of P, NP, NP-complete, NP-hard

Question

I am struggling to understand the difference between the notions $P, NP, NP-$complete, $NP-$hard. Let's take the example of the $NP-$class. We say that these problems are solved in non-polynomial time, i.e. they have an exponential time complexity, while at the same time we say that they are verified in polynomial time. What is the difference between solving and verifying in this context ? Can you give a concrete example of an algorithm in which you would show the difference between the solution and verification? Thanks.

Answer 1

Just to clear things up: these classes contain problems, not algorithms. A problem is in $P$ if there exists a deterministic algorithm that solves it in polynomial time (there could also exist one that solves it in exponential time, that's fine).

Let's take the example of the NP−class. We say that these problems are solved in non-polynomial time, i.e. they have an exponential time complexity,

Note that $P \subseteq NP$, every problem solvable in deterministic polynomial time is also solvable in non-deterministic polynomial time. So the highlighted part is wrong.

You are thinking of $NPC$ - the problems which are, in a sense, the hardest in $NP$. However, it is currently an open question whether there is no polynomial solution to them (this is the "$P$ vs $NP$" problem).

Here's an example to illustrate the difference between solving and verification and why it's plausible that verification of these problems would be faster than solving.

We'll take the classic problem $SAT$ which asks you to determine, given a boolean formula, whether there is an assignment of $true$ or $false$ to each variable that would make it true. E.g.

$(x_1 \lor x_2) \land (\neg x_2 \lor \neg x_1 \lor x_3) \land (\neg x_1 \lor x_3) $

How would you solve it? The simplest solution (by the metric of how much effort it takes to think of it) is to try all possible assignments and see if one holds; this is exponential in the number of variables. There are many ways to improve this, but we currently know of no method to solve this in polynomial time and most people believe there isn't one.

However, if I gave you an assignment, e.g. $\{ x_1 = true, x_2 = false, x_3 = true \}$ you can easily check that it satisfies the formula. Just go through the formula, substitute the variables with the value associated and use truth tables for the logical connectors. This takes linear time.

These concepts ($P$, $NP$, "easily verifiable" etc.) have rigorous definitions; I would strongly advise reading a textbook on the subject, such as:

• Hopcroft & Ullman's "Introduction to Automata Theory, Languages, and Computation"
• Michael Sipser's "Introduction to the Theory of Computation"
• Christos Papadimitriou's "Computational Complexity"

Answer 2

A simple example is integer factorization.

Finding the factors of an integer is notoriously difficult. So difficult that it is used in cryptography applications. This is a "solving" problem.

Checking that number are indeed factors of an integer is easy, by computing the remainder of the division. This is a "verifying" problem.

This concept is orthogonal to the complexity classes.

Answer 3

Consider an $n\times n$ sudoku puzzle $P$ that I give you as input, and you have to decide whether the puzzle $P$ is solvable. Formally, we consider the following language $\text{SUDOKU} = \{ \langle P\rangle: \text{$\langle P\rangle$ is a description of a solvable sudoku problem} \}$

Note that the language $\text{SUDOKU}$ contains puzzles $P$ of non-constant size.

Now if I give you a puzzle $P\in \text{SUDOKU}$ and a solution $S$ for it: so I give you a pair $\langle P, S\rangle$, then you can verify in time polynomial in $|\langle P\rangle|$ whether $S$ is a correct solution for the puzzle $P$. The latter shows that we have a polynomial time verifier for $\text{SUDOKU}$ and thus proves that the language $\text{SUDOKU}$ is in NP.

However, solving $\text{SUDOKU}$ means that given any puzzle $P$, you have to decide whether it has a correct solution $S$, which is sounds harder since you have to "prove" whether a correct solution $S$ exists (from an exponential number of candidate solutions).

In other words, on an intuitive level, checking a solution should be easier than suggesting a correct solution (unless P = NP).