Also for any problem in NP! That's useful in practice, because producing zero knowledge proofs is sooo slow. But getting non-deterministic 'hints' can speed u

Also for any problem in NP! That's useful in practice, because producing zero knowledge proofs is sooo slow. But getting non-deterministic 'hints' can speed up many computations. Crucially, the hints are arbitrary data and do not have to be computed inside the computation-to-be-proven. The most cliche example is probably verifying that a number is compound: you could either run a complicated test, or you could just 'guess' the prime factors and verify your guess via multiplication. Slightly more practical: you can sort in O(n log n) deterministic time. But that's easily beaten by Bogosort: you 'guess' a permutation, apply it to your data, and check if it's sorted. Not only does that finish in O(n) if you 'guess' right, the constant factors are also much better than for a standard sorting algorithm. Of course, your zero-knowledge computation manages to 'guess' the right permutation right away, because it gets a hint from a deterministic computer outside the 'zero-knowledge box' running the classic O(n log n) algorithm. That's still an advantage over running the O(n log n) algorithm directly, because proving computation is so expensive.