The puzzle that started complexity theory.

http://cs.nyu.edu/shasha/outofmind/mccarthypuzzle.html

by gnosis • 16 years ago

113 37 16 years ago

cs.nyu.edu

kanak• 16 years ago

Somewhat related, here's the letter that Kurt Godel wrote to John von Neumann where he describes a problem very similar to the P vs NP problem:

http://blog.computationalcomplexity.org/2006/04/kurt-gdel-19...

anonymoushn• 16 years ago

The solution doesn't seem to work on its face. If the spy simply gives the guard Y, the scheme is the same as having a bunch of fixed passwords. If the spy gives the guard X, X becomes public to the enemy. Some machine that lets the spy input X (with the input hidden to the guard) and displays Y to the guard would work, assuming the guard doesn't snoop around to discover X.

kenjackson• 16 years ago

The answers are not recycled. So after given they throw it away.

losvedir2• 16 years ago

I don't see how that solves anything. If the guard knows the answer, then you assume the enemy knows the answer. So all "throwing it away" does, is allow the enemy to cross the border once and the spy stranded!

blahedo• 16 years ago

Well, in this formulation, they're one-time passwords; but once the spy is back in the country they could get a fresh one. Of course the more complete solution would be public-key encryption, but they didn't know that yet in 1958---this idea of a one-way function is basically a precursor to that.

eru2• 16 years ago

And nowadays we would probably use the discrete logarithm problem or factoring integers as the one-way functions of choice.

tzs• 16 years ago

A chaining method can be used to reduce the frequency of the guard having to go back for a new password. Let F be the one-way function.

You give the spy a value x0. Then you compute x1=F(x0), x2=F(x1), ..., x_n = F(x_{n-1}). The guard is given x_n.

When the guard challenges the spy, the guard gives the spy x_n, the spy iterates F starting on x0 until he finds x_{n-1}, and gives that to the guard, who checks it.

The guard then replaces x_n with x_{n-1} and uses that for the next challenge, and so on. This allows for n border crossings before the spy and guard need to come to headquarters for new numbers.

Each spy can either have his own x_0, in which case the guard has to have an x_n for each spy, or you can have all the spies share the same x_0, or you can do something in between such as having the less important spies share a value and have your most important spies have their own values.

redwood2• 16 years ago

Just read your comment after posting the exact same thing above... it seems the key we both figured out is that you have a secure tool that does the work for the guard. But if this is the case then the problem isn't a problem at all: b/c with a secure tool you don't need to worry about a guard who blabbs... but that certainly didn't seem to be in the universe of hte problem that was posed

colanderman2• 16 years ago

Right; you'd actually need some sort of public-key cryptography: the guard gives the spy a challenging problem which only the spy can solve correctly, but for which anyone (including the guard) can check the answer.

mcknz• 16 years ago

original text:

Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists

http://books.google.com/books?id=-0tDZX3z-8UC&lpg=PA79&#...

Fargren• 16 years ago

The "hint" is the solution. That would be annoying for someone who hadn't figured it out.

redwood2• 16 years ago

Doesn't anyone else find the solution a bit problematic: sure great concept but unless the guards have a black box tool which is secured and can churn out Y from X, they will have to know the function to prove that Y was congruent with an X...and if they know the function, so too would the enemy. On the other hand if they have a secure tool that does this fine, but this seems to simplify the problem considerably b/c the key is that the guard doesn't need to know anything at all: the tool does all the work.

mquander• 16 years ago

The point is that knowing the function doesn't easily yield an X.

shub• 16 years ago

Let f(x) = y. The guards have f and y. A spy gives a guard an x, and the guard computes f(x) and checks it against his list of ys. If it's on the list, the spy can pass. The enemy has f and y too, but it doesn't help them! f(x) is trivial to compute but the inverse is hard, so the enemy knows exactly the answer they want the guard to get and no idea how to make him get it!

One-way functions are very cool and form the basis of public-key cryptography, although it's quite a bit more complicated than this example.

nandemo3• 16 years ago

Are you saying that the example function is truly a one-way function?

ZoFreX• 16 years ago

Define "truly one-way"! We don't have any functions that are truly one-way, just very hard to go in the other direction. This is probably easier to reverse than prime factorisation for example, but it's still asymmetric in its difficulty.

thret• 16 years ago

In real life, similar problems were solved with a shibboleth. http://en.wikipedia.org/wiki/Shibboleth Americans used 'lollapalooza' in WW2.

diiq• 16 years ago

I guess I would have failed to create complexity theory with my solution --- but everyone involved would have understood it, no long calculations required: give the guard a lock and the spy a key. It's still a sort of one-way function (easier to make a lock from a key then a key for a lock), but it doesn't require squaring 100 digit numbers in the dead of night before deciding whether to shoot a man.

philwelch• 16 years ago

Practical, literal-minded solutions are not the kind of thing that typically inspires theoretical insight into mathematics, though. That's like saying Euler could have just swum across some of the rivers in Koenigsberg.

Gupie2• 16 years ago

For what its worth, my solution was to give the guard a set of sealed envelopes. Each envelope having a password written on the outside and a password written on a piece of paper inside. The spy would give the guard the word that is written on one of the envelopes, the guard would then open the envelope and ask the spy for the password contained inside.

motxilo2• 16 years ago

How do I know that you, the creator of the password pairs, are not an enemy's spy?

The puzzle that started complexity theory.

Related Stories