1. For this we need to show it polynomial time verifiable. First we need to define a certificate. The certificate will consist of all the indices of integers in the first partition. This size of this list is bounded by the size of elements in $S$, hence it only takes up $O(n)$. To verify the algorithm it will only need to check if these indices are in the range $1,\dots,n$ and if there sum is equal to the sum of all the other integers. This only takes $O(n)$ time.
2. The certificate will be an input where the boolean formula is true. It will now evaluate the entire formula given this input. This take $O(n)$ time.
3. The decision version of this problem is: Is there a vertex cover of size smaller than k. The certificate will be the vertex cover. This is a list of all the indices inside the cover. First it will check if all the cover elements are part of the graph $O(|V||C|)=O(n^2)$. It will also check if the amount of elements in $C$ is less or equal to $k$ $O(|C|)$. And finally it will check for all edges if it has an vertex in $C$ $O(|E||C|)$. Hence it is polynomial
4. The decision version of this problem is:Is there an independant set with at least $k$ elements. The certificate will be the set of vertices. First it will check if all elements are part of the graph $O(n)$. Then it will check if the are at least $k$ elements $O(n)$. Then it will check for each edge if it has a maximum of one vertex in the set $O(|E||C|)=O(n^2)$, hence the algorithm polynomial.
5. We will make a decision problem out of it: Is it possible to pack the items in less or equal than k capacity-1 bins. It will return for each item in which bin it went. To verify, it will first check if all items are put in a bin 1 until k $O(n)$. Then it will go over all bins find all the items of that bin, add them and check if this sum is less or equal to one $O(n^3)$.
6. We will make a decision problem out of it: Is there a subset of the items with total weight at most $b$ and total total value greater than $k$. The certificate will be the subset. It will first check if the wheight is at most $b$ $O(n)$ and then check if the maximal value at least $k$ $O(n)$.