Editing Hamiltonian path problem (section)

== Polynomial time verifier ==
[[File:Hamiltonian Path Problem.jpg|thumb|221x221px|The proposed solution {s,w,v,u,t} forms a valid Hamiltonian Path in the graph G.]]
The Hamiltonian path problem is [[NP-completeness|NP-Complete]] meaning a proposed solution can be verified in [[Polynomial-time|polynomial time]].<ref name=":12"/>

A verifier [[algorithm]] for Hamiltonian path will take as input a graph G, starting vertex s, and ending vertex t. Additionally, verifiers require a potential solution known as a [[Certificate (complexity)|certificate]], c. For the Hamiltonian Path problem, c would consist of a [[String (computer science)|string]] of vertices where the first vertex is the start of the proposed path and the last is the end.<ref name=":0">{{Cite web |last=Bun |first=Mark |date=November 2022 |title=Boston University Theory of Computation |url=https://cs-people.bu.edu/mbun/courses/332_F22/slides/CS332-Lec22.pdf}}</ref> The algorithm will determine if c is a valid [[Hamiltonian path|Hamiltonian Path]] in G and if so, accept.

To decide this, the algorithm first verifies that all of the vertices in G appear exactly once in c. If this check passes, next, the algorithm will ensure that the first vertex in c is equal to s and the last vertex is equal to t. Lastly, to verify that c is a valid path, the algorithm must check that every edge between vertices in c is indeed an edge in G. If any of these checks fail, the algorithm will reject. Otherwise, it will accept.<ref name=":0" /><ref>{{Cite web |last=Bretscher |first=A |date=February 5, 2021 |title=University of Toronto CSCC63 Week 7 Lecture Notes |url=http://www.utsc.utoronto.ca/~bretscher/c63/lectures/w7.pdf}}</ref>

The algorithm can check in polynomial time if the vertices in G appear once in c. Additionally, it takes polynomial time to check the start and end vertices, as well as the edges between vertices. Therefore, the algorithm is a polynomial time verifier for the Hamiltonian path problem.<ref name=":0" />