[Solved]: Reconciling NP and the decision problem

• If $x in A$ then there exists $y$ of size at most $m|x|^m$ (here $|x|$ is the size of $x$ in bits) such that $langle x,y rangle in B$.
• If $x notin A$ then for every $y$ of size at most $m|x|^m$ it holds that $langle x,y rangle notin B$.

The string $y$ is called a witness. This definition is a bit abstract, so let me explain it using your example, the Max Cut problem. The Max Cut problem, as a set, consists of all pairs $langle G,k rangle$ such that $G$ is a graph containing a cut which cuts at least $k$ edges. The desired witness $y$ is a cut which cuts at least $k$ edges. The decision problem B consists of all pairs $langle langle G,k rangle, C rangle$ in which $G$ is a graph and $C$ is a cut in $G$ which cuts at least $k$ edges. The problem Q can be decided in polynomial time – that is, given a graph $G$, a cut $C$ in $G$, and an integer $k$, it is easy to check whether $C$ cuts at least $k$ edges. The size of $C$ is also polynomial in the size of $langle G,k rangle$. As jmite explains in the other answer, this definition is equivalent to the more usual one: NP consists of all decision problems which can be decided using non-deterministic polynomial time machines. Let me sketch why the two definitions are equivalent. Suppose first that A is in NP according to the definition stated above. The non-deterministic polynomial time machine deciding A guesses the witness $y$ and then verifies it (using the polynomial time algorithm for B), accepting if the verification succeeded. For the other direction, the sequence of non-deterministic choices functions as the witness $y$. We can verify that a specific sequence leads to acceptance by running the non-deterministic polynomial time machine using $y$ as its choices.