# [Solved]: Polynomial-time algorithm with exponential space is eligible?

Problem Detail: I’m curious about two things.

1. When we define the class called “probabilistic polynomial-time algorithm” in computer science, does it include polynomial-time algorithm with exponential space? For example, when algorithm is considered to be given a input from domain \${0,1}^n\$, what if the algorithm internally queries its exponential sized table (ex. \$0^nto0,0^{n-1}1to1\$ and so on..) and outputs the result? Does it still polynomial-time algorithm?
2. In theoretical cryptography, one-way function \$f:{0,1}^*to{0,1}^*\$ has a requirement, which is related with hard-to-invert property, as following block. If the answer to above question is yes, is it possible to construct algorithm \$A’\$ to simulate exactly same as \$f\$ for every value in \${0,1}^n\$ using exponential table as described in above question? If then, it implies that it’s impossible to design one-way function which is definitely not true. So what have i missed?

For every probabilistic polynomial-time algorithm \$A’\$, every positive polynomial \$p(cdot)\$, and all sufficiently large \$n\$’s, \$Pr[A'(f(U_n),1^n)in f^{-1}(f(U_n))]<frac{1}{p(n)}\$ where \$U_n\$ is random variable uniformly distributed over \${0,1}^n\$