Assume vertices are integers base 2.
Smallest vertex is 1.
There are n vertices.
Our input is: the number of vertices (n expressed in log(n) bits - 0s and 1s)
followed by 2 (as a separator)
followed by an edge list of n*(n-1) bits (whether or not i->j is a directed edge)
followed by a list n vertices (each vertex expressed in log(n) bits)
In terms of n, there are log(n) (n representation) + 1 (separator) + n*(n-1) + n*log(n) = m bits. Our input length is m, which is a polynomial of n.
If there is no separator, reject. We need one bit to keep track of whether or not we’ve found the separator. Accept if separator reached. Reject if end of input reached without first reaching the separator. (This probably assumes an end-of-input symbol.)
If there’s more than 1 separator, reject. We need one bit to keep track of whether or not we’ve found the separator. Accept if end-of-input reached and separator found. Reject if separator reached after already finding one.
Computing log(n) can be done in log space. Increment a counter by 1 until the separator is reached.
Subtracting 1 can be done in logspace.
Adding can be done in logspace. Can take 3 counters: Initialize a counter to 0. Subtract 1 from the first number (second counter) and add 1 to the first counter until the first number is 0. Do the same to the second number (third counter).
Multiplying can be done in logspace (Can be done with 5 log(n) counters). We need to add a number to itself n times. Four log counters are needed to do the adding (the product will be a single 2*log(n) counter). A fifth log counter is needed to count the number of additions.
Once finding the separator, confirm end of input is reached in exactly n*(n-1) + log(n)*n bits. If not, reject. We need to multiply, add, subtract 1, and know log(n), all of which is log space.
Given two integers, p and q, we can determine whether or directed edge p->q edge exists by checking the corresponding bit. We need to first compute what bit to check. Move to the separator (takes constant bits of space). Compute r = (p-1)*n + q. Go to that bit (move, decrement r by 1; stop when r is 0). It takes logspace to do this.
To process the first two vertices, first move to the separator. Then compute n*(n-1). Decrement that by 1 and move. This way we skip the edge list. Now you will be on the first vertex pair. The next 2*log(n) bits are the first two vertices, p and q. See if directed edge p->q exists.
Do this for the next two vertices (move to n*(n-1)+log(n)*offset after the separator).
We’ll need a log(n) counter to keep track of the offset (how many vertices on the path we’ve checked).
If p->q for some offset does not exist, reject.
if offset = n-1, accept.
Check that vertices are unique. Check that all vertices after the current vertex are not equal to the current vertex. Do this for each vertex. Can be done with two offset counters. (Thanks, Yuval Filmus for pointing this out!)
Because of the input length m, if all edges in the n-1 length path are valid, then it's a path of length n - a Hamiltonian path.
Is this algorithm correct? Does it verify a candidate Hamiltonian path?
Is this algorithm logspace?
