A permutation of ℕ that is computable in polynomial time, but such that no provably (in ZFC) total recursive function computes its inverse.
Inv(f) will compute a permutation, but might not be provably total. I think most of my math-related noun phrases are possible.
-
-
In that case, I return to saying might as well just say "a permutation of N that is computable in polytime, but not provably (in ZFC) onto".
-
I.e., a code for a polytime machine, which happens to be injective and surjective, but is not provably surjective.
-
I phrased it to mimic def of a 1-way function, without requirement of avg-case difficulty, but stronger requirement of worst-case difficulty
-
Ah, gotcha.
-
Actually, can prob make avg case hard too, in that no provably total recursive function agrees w/ f^-1 on non-negligible fraction of inputs.
-
Important difference is that in definition of one-way function f, function to find x from f(x) also given length(x) in unary as parameter.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.