From: tcmay@netcom.com (Timothy C. May)
And yet suppose Alice shows you one. In a textbook, for example. How did she "find" it? She likely didn't. Rather, she took 50 nodes, drew a path visiting each node once, stored this as her 'Hamiltonian cycle' and then proceeded to draw in 50 or 70 or whatever "other links," which are "ringers," as it were (that is, they are never part of the Hamiltonian she "constructed").
The resulting complete graph--50 nodes with maybe 100 or 500 or whatever links--only she knows a valid Hamiltonian cycle for (there may be others, which neither she nor anyone else will ever find).
I think something like this may be the idea behind "obfuscated computing," which Mike Duvos was writing about here a little while back. The idea is that you do this trick not just with a graph, but with a boolean circuit composed of and, or, not gates, etc. Take your algorithm and express it as such a circuit, then obfuscate it by drawing in extra gates, connections, etc. The resulting circuit has your original circuit embedded in it, but figuring out what the total circuit does can be computationally intractable. Someone could build or emulate this circuit and get a result, but they would not be able to figure out exactly what formula they were computing. I'm not 100% certain that this technique is used, but Tim's posting reminded me that I had read something about this several years ago, and this is how I remember it. Hal