Talk:UP (complexity)

Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

There is a slight problem here with one-way functions.

Indeed, Papadimitriou does show that one-way functions exists if and only if $P\neq UP$ . 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 $P\neq UP$ .

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)[reply]

|y| = O(|x|^c)

The article currently says in the definition "if x isn't in L, there is no certificate y with |y| = O(|x|^c) such that A(x,y) = 1". What does this mean? One might try to interpret this sentence as "for all functions f such that f(x) = O(|x|^c), if x isn't in L, there is no certificate y with |y| = f(x) such that A(x,y) = 1" or "there exists a function f such that f(x) = O(|x|^c) and if x isn't in L, there is no certificate y with |y| ≤ f(x) such that A(x,y) = 1" but these don't make much sense. Or is "|y| = O(|x|^c)" here just a mistake and it should simply be "if x isn't in L, there is no certificate y such that A(x,y) = 1"? 90.190.113.12 (talk) 21:21, 10 April 2013 (UTC)[reply]

|y| = O(|x|c)

|y| = O(|x|^c)