NP and NP-complete Definitions ============================== You might have heard that a certain problem is NP and cannot be solved. But what does that really mean? And why can't it be solved? In this chapter, we will examine these issues. The goal of this chapter is to determine the status of graph problems for which we have not provided an algorithm. This chapter justifies our failure to provide practical algorithms for these problems. This topic is one of the subjects of theoretical computer science. Although reading this chapter will not directly help your success in computer Olympiad exams, reading it is recommended for the following reasons: - This topic is one of the most interesting in theoretical computer science, and you, as someone interested in the Computer Olympiad, will definitely enjoy it. - Reading this topic will help you avoid common misconceptions among students about NP problems. - Reading this topic will help you more easily identify NP problems and avoid trying to solve them in exams. Decision Problems ----------------- Decision problems are problems whose answer is only a single bit. That is, their answer is either yes or no. For example, the problem "factorize a number" is not a decision problem, but "is a number prime or not" is a decision problem. Generally, for problems, there exists a corresponding decision problem that can be used to solve the main problem. For instance, the decision problem "is the smallest prime factor of this number greater than k or not" can solve the factorization problem with the help of a 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 deal with decision problems, but the results can be broadly applied to other problems as well. Class P ------- Problems in class P are a category of decision problems for which an algorithm exists that can determine the result in :math:`O(|s|^k)`. 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, problems that are solvable in polynomial time with respect to the input length are in this class. Note that input length is not always the parameter by which we analyze algorithm complexity. For example, the decision problem for number factorization, i.e., "does number :math:`n` have a prime factor smaller than :math:`k`", has an algorithm with a time complexity of :math:`O(\sqrt{n})` or :math:`n^{\frac{1}{2}}`, but this problem is not in class P. This is because the input length is :math:`O(lg(n))`, meaning our algorithm was not polynomial with respect to the input length. Class NP -------- These problems are a category of problems that do not necessarily have a polynomial-time solution but do have a polynomial-time verifier. Verifier ~~~~~~~~ A verifier for a problem is itself a decision problem that takes the original problem's input along with an auxiliary string (called a solution or proof) and determines whether this solution is correct for the problem. If an auxiliary string exists that the verifier accepts, it means the answer to the main problem is positive. If the answer to the main problem is negative, no string exists that the verifier will accept. More precisely, if we denote the main problem by :math:`X`, where :math:`X(s)` is either accepted or rejected, we call a problem like :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 any possible string t, :math:`C(s,t) = 0`. - If :math:`X(s) = 1`, then at least one string t exists such that :math:`C(s,t) = 1`. Definition ~~~~~~~~~~ Now, we return to the definition of class NP. A problem is a member of this class if and only if it has a verifier that reaches a conclusion in polynomial time, and also, if the answer to the main problem is positive, an auxiliary string of polynomial length relative to the input exists that the verifier accepts. Example ~~~~~~~ A wide range of problems falls into this class. For example, consider the problem of whether a graph has a Hamiltonian cycle. A verifier can take a permutation of vertices as input and check if each member of this permutation has an edge to its next member. If the answer to the main problem is negative, no such permutation exists. If it is positive, a permutation exists whose length is less than that of the original graph, and the verifier can perform this check in linear time. Thus, the Hamiltonian cycle problem is an NP-class problem. The corresponding decision problem for integer factorization is also an NP problem. A verifier can take a number smaller than :math:`k` as input and determine whether the input is divisible by this number. This determination can perform division in polynomial time (with the help of the algorithm we learned in elementary school), and the length of the proof (the number smaller than :math:`k`) is less than the length of the input. Therefore, this problem is also in class NP. Polynomial Time Reduction ------------------------- We define problem A to be polynomially reducible to problem B if and only if problem A can be solved in polynomial time with the help of an algorithm and an oracle machine for problem B. Reduction is important because if A reduces to B and B can be solved in polynomial time, then A can also be solved in polynomial time. NP-hard and NP-complete Problems -------------------------------- A problem is called NP-hard if and only if every problem in class NP can be polynomially reduced to it. If an NP-hard problem is itself in class NP, it is called NP-complete. It might seem strange that all problems, which have a vast and immense diversity, can be reduced to a single problem, but later in this chapter, you will become familiar with many NP-hard and NP-complete problems. P=NP ---- This problem is the biggest open problem in all of computer science. It asks whether all problems in class NP can be solved in polynomial time or not. This problem is equivalent to whether one of the NP-hard problems can be solved in polynomial time. A positive answer to this problem would break all encryption algorithms and has the potential to collapse the economy. On the other hand, it would compute computational problems that currently take billions of years in a short amount of time. It could find the key to curing cancer, and so on. A negative answer to this problem, although it has no practical application and the common belief is that the answer is negative, would still be a tremendous advancement in theoretical computer science. A million-dollar prize has been offered for proving this problem.