# The complexity class NP

More formally, let $I=\bigcup_{n=1}^\infty\{0,1\}^n$ and let $f:I\rightarrow\{0,1\}$ be a Boolean function. We say that f belongs to NP if there is a polynomial p and a function $g:\bigcup_{n=1}^\infty\{0,1\}^{n+p(n)}\rightarrow\{0,1\}$ such that g belongs to P, and such that f(x)=1 if and only if there exists y such that g(x,y)=1.