  NP is sometimes described as the set of problems, \(S\), that have short proofs of membership. For example, suppose we are given a list of \(m\) large natural numbers: \(a_{1}, \ldots ,a_{m}\), and a target number, \(t\). This is an instance of the Subset Sum problem: is there a subset of the \(m\) numbers whose sum is exactly \(t\)? This problem is easy to solve in nondeterministic linear time: for each \(i\), we guess whether or not to take \(a_{i}\). Next we add up all the numbers we decided to take and if the sum is equal to \(t\) then accept. Thus the nondeterministic time is linear, i.e., some constant times the length of the input, \(n\). However there is no known (deterministic) way to solve this problem in time less than exponential in \(n\).