# NP problem A class of problems that can be efficiently verified if a suggested input actually solved it. This is very interesting because it helps to define a class of common problems based on their verification procedure. The verification is done by producing an algorithm that accept two inputs: an instance of a problem (e.g., a graph) and proposed solution (e.g., Hamilton cycle) and decide in polynomial time whether the proposed solution solve the problem instance or not. SAT is in NP as any proposed solution for SAT can be efficiently verifiled. Moreover, SAT is [[NP hard problem]] : because solving it will solve all NP problems as follows. The verification algorithm is easily transformed (efficiently) to a SAT by describing it as UTM and having as input to the UTM a proposed solution. The inputs are the free parameters in SAT. If SAT is accepted then this means that a solution exist and if rejected then no solution exist. To repeat the point - SAT is a [[NP-Complete problem|hardest problem]] in NP (and all problems that can be reduce from it) because solving SAT enable solving in polynomial time all other NP problems. Examples: - NP problem - given a formula with boolean parameters, decide if there exist a boolean value for each parameter such that the formula output “True”. - Non-NP problem - find the length of the shortest vector in a lattice (up to a polynomial factor - polynomial in the lattice dimension). It is not NP as there is no known efficient way to verify that a suggested vector is really the shortest in the lattice. This is probably and definite as there is a small chance that someone will find such efficient method. - Non-NP problem - the halting problem. It is not NP as it is not decidable i.e., given an algorithm an its input - there is no efficient algorithm that determine if the algorithm will halt for this input. ## $P\subset NP$ Based on [^1]. Let assume we have an algorithm $A$ that decide on an input in a polynomial time. Define an NP verifier that takes it can be used as an oracle. The NP algorithm a problem belongs to $P$ if it can be solved in polynomial time. this means that there is an algorithm $A$ that terminates after $q(n)$ steps on input size $n$. We can give $A$ all strings with size at most $q(n)$ as input (the max number of steps bound the input size), each run will take --- ## NP can be defined with Nondeterministic Turing Machine (NTM) NP is the class of problems that are solved by an NTM. ## Why are the two NP definitions equivalent? Existence of polynomial verifier $\rightarrow$ NTM exist: an NTM can run the verifier simultaneously on all branches that are correlated to all strings in the input space (exponential size). This run takes polynomial time (this is the definition of NTM). The NTM accept the input if any of the branches is a solution for the problem. note: that the definition of NTM map each branch to different computation and not different input - but I guess these two are equivalent. #math #tech ## Created 2023-04-23 13:25 [^1]: [[@computers and intractability a guide to the theory of NP completeness]]