Last year I attended a workshop at Princeton entitle "Impagliazzo's Worlds" (named after Russell Impagliazzo who started this line of inquiry) about life would be like (complexity wise) re: the P = NP? problem. It turns out to be much more varied than I would have thought. I've stolen what's below from Lance Fortnow's blog. Note, especially "Pessiland". Victor In that paper he describes five possible worlds and their implications to computer science. Algorithmica: P = NP or something "morally equivalent" like fast probabilistic algorithms for NP. This was the world I described last week but looking back at Impagliazzo's paper, he does a nicer job. Heuristica: NP problems are hard in the worst case but easy on average. Pessiland: NP problems hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. This is the worst of all possible worlds, since not only can we not solve hard problems on average but we apparantly do not get any cryptographic advantage from the hardness of these problems. Minicrypt: One-way functions exist but we do not have public-key cryptography. Cryptomania: Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels. Impagliazzo does not guess which world we live in. Most computer scientists would say Cryptomania or Minicrypt. On Wed, Feb 13, 2013 at 11:37 PM, Andy Latto <andy.latto@pobox.com> wrote:
On Wed, Feb 13, 2013 at 8:47 PM, Warren Smith <warren.wds@gmail.com> wrote:
Much or all of cryptography depends on the claim that there is a bijective map F such that computing y=F(x), is a lot easier than computing x=Finverse(y).
For example, if F maps (a,b,c) to (b^a mod c, b, c) where gcd(b,c)=1, then many people think/hope that Finverse is a lot harder than F ("discrete logarithm problem").
But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"?
The problem is that what you'd really like is an example where F can be computed in polyomial time, but Finverse cannot. But if F is in P, then Finverse is in NP, so proving that any F has this property is at least as hard as proving that P != NP.
Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun