Talk:UP (complexity)
![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||
|
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)
|y| = O(|x|c)
[edit]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), and for any x not 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 for any x not in L, there is no certificate y with |y| ≤ f(x) such that A(x,y) = 1" etc. but these don't make 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)
Start a discussion about improving the UP (complexity) page
Talk pages are where people discuss how to make content on Wikipedia the best that it can be. You can use this page to start a discussion with others about how to improve the "UP (complexity)" page.