How to show that problems are in NP?

I want to show that the following problems are in NP (NP-completeness is irrelevant) by textually describing a non-deterministic Turing machine which runs in polynomial time. The assumptions are that addition, multiplication, tests for divisibility can be done in polynomial time and natural numbers are represented in binary.

a) $\{n \in \mathrm{N} \ | \ n \ $is not a prime number$\}$

b) $\{x_1, ..., x_n, y \in \mathrm{N} \ | \exists M \subseteq \{1, ..., n\} : \sum_{m \in M}x_m = y \ \}$

For a) it's clear that there must be a non-trivial divisor if $n$ isn't a prime, but how does it exactly work? How can I reject invalid and verify valid inputs?

The easiest way to prove some problem is in $\mathsf{NP}$ is using the certificate definiiton of $\mathsf{NP}$ mentioned in other answers. The nondeterministic definition of $\mathsf{NP}$ is usually not very useful for showing a problem belongs to $\mathsf{NP}$. Intuitively, a problem is in $\mathsf{NP}$ iff we have an efficient (polynomial time) verification algorithm with polynomial size certificates/proofs.

For example, if you want to check if a given number $m$ is composite,
the following works:

• Format of certificates: certificates are a pair numbers $(a, b)$,

• Verification algorithm: a certificate $(a,b)$ is accepted iff $1

If a number is composite then there is a pair of number $(a,b)$ which satisfies the condition and has size $O(\lg m)$. It is important that the certificate has polynomial size in the size of input (here the size of input is $\lg m$).

If a number is not composite there are no such pairs.

Note that we fix a particular certificate verifier for all inputs. You cannot change the verification algorithm from one input to another one.

A more challenging question is to show that primeness is also in $\mathsf{NP}$, i.e. there are polynomial size primality certificates.

StackExchange Computer Science Q#12969, answer score: 7