# NP problem A class of problems with the property that given a solution - it can be efficiently verified. The verification is done by providing an algorithm that accept two inputs: an instance of a problem (e.g., a graph and a question if it contains Hamilton cycle) and a proposed solution (e.g., a description of an Hamilton cycle in that graph) and decide in polynomial time whether the proposed solution solve the problem instance or not. ## 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”. This is called the SAT problem. - 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. - 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. #math #tech ## Created 2023-04-23 13:25 [^1]: [[@computers and intractability a guide to the theory of NP completeness]]