 Certificate (complexity)

A certificate for a positive instance is a polynomial-length string that makes a polynomial-time verifier accept that instance.