Talk:UP (complexity)
From Wikipedia, the free encyclopedia
There is a slight problem here with one-way functions.
Indeed, Papadimitriou does show that one-way functions exists if and only if . However, he uses a non-standard definition of one-way function. This is explained in detail in his book. I quote from page 285: A definition of one-way functions that is closer to what we need in cryptography would replace requirement (iii) -- that inverting is worst-case difficult -- by a stronger requirement [...]
This is a big difference, and it is (as far as I know) unknown whether one-way functions are implied by .
- I've removed it. The definition isn't really "nonstandard" per-se, it is just the worst-case definition of one-wayness, used only in structural complexity instead of cryptographic complexity. I also removed a similar reference to worst-case one-way functions from the one-way function article. Blokhead 18:58, 23 October 2005 (UTC)