At 12:59 PM -0400 10/11/00, Marcel Popescu wrote:
An interesting idea has surfaced on the freenet-chat list: is it possible to build a program that creates some sort of a puzzle, whose answer the generating computer knows (and can verify), but which can only be answered by a human being, not by a computer? [Additional requirement: it should be easy for the human to answer the puzzle.]
There are not any examples that I know of that are exponentially harder for computers to solve than for humans to solve. There may be examples which polynomially harder for computers to solve (e.g., 1000 800 MHz Pentium IIIs for 3 hours vesus a single human for one second), but this is not interesting from a crypto perspective. --Tim May -- ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, "Cyphernomicon" | black markets, collapse of governments.