Polynomial time functions can be made provably total. But yes, 2nd condition says no provably surjective recursive function computes it.
-
-
Replying to @ModelOfTheory
Right, I was just saying "computes its inverse" is needlessly wordy compared to "computes it".
1 reply 0 retweets 0 likes -
Replying to @RadishHarmers @ModelOfTheory
To code n which computes function f, we can easily associate code Inv(n) which computes f^{-1} (choosing, say, minimal preimages).
1 reply 0 retweets 0 likes -
Replying to @RadishHarmers @ModelOfTheory
Ah, but all these things you post are half the time impossibilities anyway, I forgot…
1 reply 0 retweets 0 likes -
Replying to @RadishHarmers
Inv(f) will compute a permutation, but might not be provably total. I think most of my math-related noun phrases are possible.
1 reply 0 retweets 0 likes -
Replying to @ModelOfTheory
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".
1 reply 0 retweets 0 likes -
Replying to @RadishHarmers @ModelOfTheory
I.e., a code for a polytime machine, which happens to be injective and surjective, but is not provably surjective.
2 replies 0 retweets 0 likes -
Replying to @RadishHarmers
I phrased it to mimic def of a 1-way function, without requirement of avg-case difficulty, but stronger requirement of worst-case difficulty
1 reply 0 retweets 1 like -
-
Replying to @RadishHarmers
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.
1 reply 0 retweets 0 likes
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.
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.