Hamiltonian cycle problemet (HAM-CYCLE)

Gitt en rettet graf, $G=(V,E)$, eksisterer det en enkel sykel som går innom alle noder i grafen? Dette er et NP problem, fordi det har ingen kjent løsning i polynomisk tid, men vi kan enkelt verifisere et forslag til løsning/sertifikat i polynomisk tid.