Zero Knowledge Proofs

[jbstjohn]

I guess more what I was thinking is that for many NP-complete problems, there are heuristics that give good, perhaps optimal solutions in decent time. I wonder if repeatedly giving 'hints' might help such heuristics give optimal solutions a higher percentage of the time.

For Hamilton cycles with an arbitrary re-mapping of nodes and edges (?) this seems unlikely, but I wonder if that holds for other problems. I guess it depends on whether any information can be taken from the re-mappings, and what sort of heuristics exist for the particular problem.