a certificate and verifier
Think of a maths exam where the hard part is finding a proof, but checking a proof someone else wrote is comparatively easy. The proof is a CERTIFICATE — a short piece of evidence that the answer is 'yes' — and the grader who reads it and says 'valid' or 'not valid' is the VERIFIER. This pair captures, in plain mechanical terms, what it means for a problem to be in NP: 'yes' instances must come with checkable evidence, and the checker must be fast.
Formally, a verifier for a problem is a deterministic algorithm V(x, c) that takes the problem input x and a candidate certificate c and outputs accept or reject. We require two things. Completeness: if x is a 'yes' instance, there EXISTS a certificate c (of length polynomial in |x|) with V(x, c) = accept. Soundness: if x is a 'no' instance, then for EVERY c, V(x, c) = reject. And V must run in time polynomial in |x|. The certificate is the 'answer key' that turns an exhausting search into a quick check; the verifier is the trustworthy grader that cannot be fooled by a bogus key. A problem is in NP precisely when such a polynomial-time verifier exists. Concretely, for graph 3-colouring the certificate is a colour for each vertex; the verifier scans every edge and accepts only if its two endpoints differ — clearly polynomial, and impossible to satisfy if no proper colouring exists.
Two subtleties matter. First, the certificate must be SHORT (polynomial length) — if you allowed an exponentially long hint you could smuggle in the whole brute-force search and the notion would be meaningless. Second, the asymmetry: NP guarantees checkable evidence for YES answers, not for NO answers. There is no requirement that 'this graph is NOT 3-colourable' has a short certificate; whether NO-answers always have short proofs is exactly the open co-NP question. The verifier/certificate picture is the most intuitive door into NP and into reductions, because proving membership in NP usually just means describing the certificate and the checker.
Hamiltonian cycle: 'does this graph have a cycle visiting every vertex exactly once?'. Certificate: the proposed ordering of vertices v1, v2, ..., vn, v1. Verifier: check each consecutive pair is an edge and that all n vertices appear once — O(n) work. If the graph truly has such a cycle, this certificate exists; if not, no ordering passes.
Certificate = short evidence for 'yes'; verifier = fast checker that no bogus evidence can fool.
The verifier must be SOUND: on a 'no' instance, no certificate may slip through. A checker that accepts some false proof does not show membership in NP. And membership in NP says nothing about NO-instances having short proofs — that is the separate question of co-NP.