Let M0,M1,M2,M3,... be some canonical enumeration of Turing machines,
and let M be the Turing machine that takes a graph as input and works as follows:
Set i=0. 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 2i-j steps.
(After that for loop, but still inside the while loop,) Increase i by 1.
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))
?