Let M0,M1,M2,M3,... be some canonical enumeration of Turing machines. (Enumerations for
which the indices are polynomially related will yield the same answer to the question at the end
of this post.) Let M be the Turing machine that takes a graph as input and works as follows:
Set i=1. While none of the machines has outputted a Hamiltonian cycle in the graph:
For j in {0,1,2,3,...,i-1,i}, simulate Mj on the graph until it halts or has run for i steps.
(After the for loop, but still inside the while loop,) Increase i by 1.
When at least one of the machines has outputted a Hamiltonian cycle in the graph, halt.
Let T be the function from graphs to {0,1,2,3,...} given by
if M(G) halts then T(G) is the time M(G) runs for, else T(G) = 0 .
With those definitions, the question could be interpreted as the following:
Are there functions f and g from {0,1,2,3,...} to (0,∞) such that
f is in nω(1) and g is in 2^(no(1)) and for all elements n of {0,1,2,3,...}, f(n) < g(n)
and there is a zero-knowledge proof for the promise problem
Input: a graph G with a Hamiltonian cycle
must output YES if: g(size(G)) < T(G)
must output NO if: T(G) < f(size(G))
?