Re: A Mathematical One-Way Function.

On Oct 25, 1:49 pm, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>
wrote:
jbriggs444  <jbriggs...@xxxxxxxxx> wrote:
Informally speaking, "hard" problems are those problems whose
answers are too big to print.  Not those problems whose answers
are too hard to compute.  That's uninteresting.

Something went wrong in the translation from formal to informal.

From formal to formal to informal. I think it's a quantifier order
issue. Mark Wooding had it that the choice of TM could be made
after the problem instance had been selected. Wiki requires the
TM to be fixed first. Wiki's version makes more sense.

Try reading the Wikipedia definition as well, and compare.

Right. Some of the same pieces, but not at all the same
definition.

Concretely, we get a (t,eps)-one-way function f:U->V such that for
any A using time at most t (running on some fixed non-stupid computer,
counting the size of the program as part of its time cost),

        Pr[ f(A(f(x))) = f(x) ] <= eps,

where x is sampled from the uniform distribution on U .

OK, that seems reasonable. All nice and finite so that you
can have that uniform distribution on a countable space.

Thank you for the pointers.
.