[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhnon_polynomial_time.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Non-Polynomial Time" source: https://www.jemoka.com/posts/kbhnon_polynomial_time/ --- \begin{equation} NP = \bigcup_{k \in N} \text{NTIME}\qty(n^{k}) \end{equation} Meaning, these are problems with the property that once you “have” the solution, its “easy” to verify the solution. verifier formulation of NP \(L \in \text{NP}\), if there exists a Polynomial Time turing machine named \(V\) (called a “verifier”) such that: \begin{equation} X \in L \Leftrightarrow \exists\ w \in \qty {0,1}^{\text{poly}\qty(|x|)} V(x,w) = 1 \end{equation} that is, “yes instances have efficiently checkable certificates/“proofs”