Certificate (complexity)
= Certificate
{disambiguate=complexity}
{wiki}
A certificate for a positive instance is a polynomial-length string that makes a polynomial-time verifier accept that instance.
= Certificate in computational complexity
{synonym}