A permutation of ℕ that is computable in polynomial time, but such that no provably (in ZFC) total recursive function computes its inverse.
Polynomial time functions can be made provably total. But yes, 2nd condition says no provably surjective recursive function computes it.
-
-
Right, I was just saying "computes its inverse" is needlessly wordy compared to "computes it".
-
To code n which computes function f, we can easily associate code Inv(n) which computes f^{-1} (choosing, say, minimal preimages).
-
Ah, but all these things you post are half the time impossibilities anyway, I forgot…
-
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.
- 2 more replies
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.