G be a graph
H be the set of Hamiltonian paths in
G has a Hamiltonian path, then by systemically changing our start vertex and then nondeterministically walking the remaining
N vertices, we will find it (i.e. take a "random walk").
Can we nondeterministically walk such that if there's a Hamiltonian path, we'll choose the least next vertex? Let's call this the least Hamiltonian path.
For example, let
G1 be a graph with
3 vertices and all possible edges
Then there are 6 elements of
G1, if our start vertex is
3, then there are 2 Hamiltonian paths:
By nondeterministically choosing the least next vertex of the Hamiltonian if one exists, then we'll always choose the same Hamiltonian path:
312 in this case (because our start is
If we are allowed to nondeterministically choose the least next vertex, then we can nondeterministically traverse the same Hamiltonian path multiple times.
We ensure the least Hamiltonian path has no duplicate vertices. Pseudocode:
function hasDuplicates(leastHPath): for (j in N): for (k in N): if (k == j) continue; if (leastHPath[j] == leastHPath[k]: return false; return true;
Does this algorithm (nondeterministically choosing the least Hamiltonian path if one exists, ensuring the count of vertices = N and ensuring there are no duplicates) decide Hamiltonian paths? If so, what is its space complexity?