P, NP, and NP-hard Completeness
What is P Class of Problem？
A problem has a polynominal algorithm means that it can be solved in polynominal time with respect to the size of inputs. We also call the problem as P problem.
Version of Problem
We have three version of problems. We consider problems where we have one “cost” that we want to minimize.
- Optimization: Given a problem instance, find the minimum cost solution.
- Evaluation: Given a problem instance, find the cost of the min-cost solution.
- Recognition: Given a problem instance and an integer L, is there a solution with cost no greater than L?
Note that the third version requires only a “yes-no” answer. This makes the discussion easier, and we will focus on Recognition problems. Depending on assumptions about the cost function, it can be shown that the three problem formulations are equivalent.
What is NP Class of Problem
Intuitively, this is the class of problems that given a problem instance and guess for a solution, we can verify in polynomial time, whether the guess is a correct solution.
Polynomial verification of a solution
For a reconization problem, if we are given a guess of solution, we want to verify whether this solution can help us answer this problem.
If we can “doublecheck” that the guess is a solution of the problem in polynomial time, we say that we can verify the problem in polynomial time.
Non-Deterministic Algorithm
Let’s imagine an algorithm for reconization problem, it somehow come up with a solution which may be generated by a guess, and check the cost of solution is less than L.
Therefore the algorithm can be decomposed in two parts: guessing and verifying
We call all problem instances for which answer is yes as yes-instance (There exists a solution of cost is less than L in a problem instance).
If a problem instance is a yes-instance, assuming we are good at guessing, we will find its solution with the first try, then we can solve the reconization in polynomial time:
\[guessing + poly.verification.\]However we can use this algorithm to solve the non-yes-instance (there is no solution with cost is less than L), because we have no way to prove that there is no such solution.
The NP Class
A problem belongs in Non-deterministic Polynomial class, if yes-solution of the problem can be verified in polynomial time.
WWFs (Well-Formed Fomulas)
There are eight WFFs: \(\begin{array}{ll} All \ A \ is \ B & x \ is \ A \\ no \ A \ is \ B \ & x \ is \ not \ A \\ some \ A \ is \ B & x \ is \ y \\ some \ A \ is \ not \ B & x \ is \ not \ y \end{array}\)
All the sentences not aforementioned are not WFFs.