A Turing machine that decides LR is called a verifier for L and a y such that (x, y) ∈ R is called a certificate of membership of x in L. In general, a verifier does not have to be polynomial-time.
O mașină Turing care decide LR se numește un verificator pentru L și un y astfel încât (x, y) ∈ R se numește un certificat de apartenență al lui x în L. În general, un verificator nu trebuie să fie în timp polinomial.