If you express the inputs in unary you get a different running time than if you express them in a higher base (binary, most commonly).
So the question is, for subset sum, what base is appropriate? In computer science we normally default to the following:
- If the input is a list or collection, we express its size as the number of items
- If the input is an integer, we express its size as the number of bits (binary digits)
The intuition here is that we want to take the more "compact" representation.
So for subset sum, we have a list of size $n$ and a target integer of value $t$. Therefore it's common to express the input size as $n$ and $t=2^k$ where $k$ is the number of bits needed to express $t$. So the running time is $O(n 2^k)$ which is exponential in $k$.
But one could also say that $t$ is given in unary. Now the size of $t$ is $t$, and the running time is $O(n t)$, which is polynomial in $n$ and $t$.
In reductions involving subset sum (and other related problems like partition, 3-partition, etc) we must use a non-unary representation if we want to use it as an NP-Hard problem to reduce from.
The requirement for NP is that we want the algorithm to have the property that a problem instance is affirmative if and only if there is a certificate such that the algorithm accepts the problem instance with that certificate. That is, a set $A$ is in NP when there is an algorithm $p$ such that $x\in A$ if and only if there is $y$ such that $p$ accepts $(x,y)$, and $p$ runs on every $(x,y)$ in polynomial time of $|x|$.
If I understand you, you are proposing that the certificate $y$ should simply be an indicator for whether $x\in A$ or not. That is, your algorithm would seem to accept all input of the form $(x,{\it \text{yes}})$, and reject otherwise. With this algorithm, you will indeed have the property that $x\in A$ implies there is $y$ such that $p$ accepts $(x,y)$, since we can let $y$ be yes. But you will not achieve the reverse implication, since your algorithm will accept $(x,y)$ whenever $y$ says yes, and so it has the capacity to be fooled, accepting $(x,{\it\text{yes}})$ even when $x\notin A$, when we do not want it to be accepted.
The point of NP is that problems are in NP when they can be set up in the certificate style, so that an acceptable certificate exists only for the inputs that are truly in the set. So, in the case of the 3-sat problem, for example, a Boolean expression has a satisfying instance if and only if there is an assignment of the Boolean variables making the expression true. So the certificate will be the variable assignment, and it can be checked whether such a certificate is correct in polynomial time.
Perhaps it will help you to observe that $x\in A$ does not necessarily imply that $p$ accepts every $(x,y)$, only that there is a $y$ which $p$ accepts. In particular, just because $p$ rejects a particular $(x,y)$, it doesn't mean that we may conclude that $x\notin A$; instead, it just means that we haven't yet verified $x\in A$, and perhaps it may be impossible to verify this, but we can't be sure yet.
Best Answer
For such a set to be a certificate for the complement of SUBSET SUM the verifier not only has to verify that each subset in the certificate sums to a non-zero value. The verifier also has to verify that every subset in the certificate is derivable from the original set and verify that no additional subsets beyond those in the certificate can be derived. If your verifier does all that, then you have a verifier and a certificate. But since this is equivalent to brute-force solving the problem twice (once to generate the certificate, once to verify the certificate), it's kind of pointless. Brute-forcing the problem once is infeasible enough.