.. _np-definition: Definition of NP and NP-Completeness ==================================== You may have heard that a certain problem is in **NP** and cannot be solved. But what does this really mean? And why can't it be solved? In this chapter, we will explore these questions. The goal of this chapter is to address graph problems for which we did not provide algorithmic solutions. It justifies our failure to present a practical algorithm for these problems. This topic belongs to theoretical computer science. Although studying this chapter will not directly contribute to your success in computer olympiad exams, it is recommended for the following reasons: - This is one of the most fascinating topics in theoretical computer science, and as someone interested in computer olympiads, you will undoubtedly enjoy it. - Studying this topic will help you avoid common misconceptions about NP problems among students. - Studying this topic will help you more easily recognize NP problems and refrain from attempting to solve them in exams. Decision Problems ----------------- Decision problems are those where the answer is a single bit. That is, their answer is yes or no. For example, the problem of factoring a number is not a decision problem, but determining whether a number is prime is a decision problem. Generally, for many problems, there exists a decision problem that can solve the main problem. For example, the decision problem "Is the smallest prime factor of this number greater than k?" can solve the factorization problem using binary search. In general, the decision problem "Is the k-th bit of the output 1?" can solve the main problem. In this section, we primarily deal with decision problems, but the results can be widely applied to other types of problems as well. .. raw:: latex \begin{class}P}\end{class} Class P --------- Problems in class P are a set of decision problems for which there exists an algorithm that can determine the result in :math:`O(|s|^k)` time. Here, :math:`s` is the input string, :math:`|s|` is the length of the input string, and :math:`k` is a constant independent of the input. In other words, this class includes problems solvable in polynomial time relative to the input length. Note that the input length is not always the parameter used to analyze an algorithm's complexity. For example, consider the decision problem of integer factorization: determining whether a number :math:`n` has a prime factor smaller than :math:`k`. This problem has an algorithm with time complexity :math:`O(\sqrt{n})` (or equivalently :math:`n^{\frac{1}{2}}`), but it does not belong to class P. This is because the input length is :math:`O(\lg(n))`, meaning the algorithm's runtime is not polynomial with respect to the input length. .. code-block:: text NP Class --------- These problems are a category of problems that do not necessarily have a polynomial-time solution, but have a polynomial-time verifier. Verifier ~~~~~~~~~~~~~ A verifier for a problem is itself a decision problem that takes the input of the original problem along with an auxiliary string (called an answer or proof) and determines whether this answer is correct for the problem or not. If there exists an auxiliary string that the verifier accepts, it means the original problem's answer is positive. If the original problem's answer is negative, no string exists that the verifier would accept. More precisely, if we denote the original problem by :math:`X`, where :math:`X(s)` is either accepted or rejected, we call a problem :math:`C(s,t)` a verifier for problem X if and only if the following two conditions hold: - If :math:`X(s) = 0`, then for every possible string t, :math:`C(s,t) = 0`. - If :math:`X(s) = 1`, then there exists at least one string t for which :math:`C(s,t) = 1`. .. _definition: Definition ~~~~~~~~~~ Now we return to the definition of the NP class. A problem belongs to this class if and only if it has a verifier that terminates in polynomial time, and furthermore, if the answer to the original problem is affirmative, there exists an auxiliary string with polynomial length relative to the input that the verifier will accept. Example ~~~~~~~ A wide range of problems fall into this class. For example, consider the problem of whether a graph contains a Hamiltonian cycle. A verifier can take a permutation of vertices as input and check whether each member of this permutation is connected by an edge to the next member. If the answer to the main problem is negative, no permutation exists; if positive, there exists a permutation whose length is shorter than the original graph, and the verifier can perform this check in linear time. Thus, the Hamiltonian cycle problem belongs to the class ``NP``. The corresponding decision problem of number factorization is also an ``NP`` problem. A verifier can take a number smaller than *k* as input and determine whether the input is divisible by this number. This check can be performed in polynomial time via division (using the algorithm we learned in elementary school), and the proof length (the number smaller than *k*) is shorter than the input length. Therefore, this problem also lies in the class ``NP``. .. _polynomial-reduction: Polynomial Reduction -------------------- We define that problem **A** is polynomial-time reducible to problem **B** if and only if, using an algorithm and an oracle machine for problem **B**, problem **A** can be solved in polynomial time. Reduction is important because if **A** reduces to **B** and **B** is solvable in polynomial time, then **A** is also solvable in polynomial time. .. _np-hard-vs-np-complete: NP-Hard and NP-Complete Problems ------------------------- A problem is called **NP-hard** if and only if every problem in the NP class can be reduced to it in polynomial time. If an NP-hard problem itself belongs to the NP class, it is called **NP-complete**. It may seem surprising that all problems with their vast diversity can be reduced to a single problem. However, throughout this chapter, you will become familiar with numerous NP-hard and NP-complete problems. .. code-block:: python :linenos: # in tabe yek tike az yek graph ra mishkanad def graph_cut(graph): # cut logic return cut_graph P=NP -------- This problem is the biggest open question in all of computer science. It asks whether all problems in the NP class can be solved in polynomial time. This problem is equivalent to determining whether any NP-hard problem can be solved in polynomial time. A positive answer to this problem would break all encryption algorithms and has the potential to collapse global economies. On the other hand, computational problems that currently require billions of years to solve could be computed in short time spans. It could unlock solutions to curing cancer, and... A negative answer to this problem, while lacking practical applications (and despite the general consensus leaning toward a negative answer), would represent a monumental breakthrough in theoretical computer science. A one-million-dollar prize has been offered for resolving this problem.