4
$\begingroup$

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^n\to0,0^{n-1}1\to1$ 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$

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ To your first question, if it reads exponential much space, then it must use exponential much time. However, if it has access to an exponential size table (constructed beforehand?), but only reads polynomially many entries, then it runs in polynomial time. However, how can it, for every $n$, have constructed table. This can only happens if $n$ is considered constant, in which the algorithm runs again in polynomial time. $\endgroup$
    – John Kemeny
    Commented Aug 7, 2013 at 11:12
  • $\begingroup$ @PålGD, could you explain more that why pre-constructed table only happens if $n$ is considered constant? In theory of computation, is there no way to formalize the existence of such pre-constructed table, with any complexity in $n$? $\endgroup$
    – euna
    Commented Aug 8, 2013 at 4:17
  • $\begingroup$ Yuval has an excellent answer below where he addresses this. $\endgroup$
    – John Kemeny
    Commented Aug 8, 2013 at 8:12

2 Answers 2

Reset to default
10
$\begingroup$

Regarding your first question, what you're missing is where your "exponential table" comes from. Your algorithm has a finite description and should work for every $n$. So it cannot explicitly contain the $n$-table for all $n$. It could contain instructions for computing the table, but then it would have to first execute them, and constructing an exponential size table takes exponential time.

On the other hand, your program could use a (supposedly) exponential amount of uninitialized space. Since its running time is polynomial, it only accesses polynomially many cells. You can implement memory access in such a way that if $T$ cells are ever accessed then $\tilde{O}(T)$ memory is used (exercise). The corresponding running time might become much worse, but still polynomial.

A third possibility are non-uniform computation models, which are popular in cryptography. Here the idea is that the algorithm is allowed to use a certain hard-coded amount of data which depends only on $n$. However, this data has to be polynomial size. This restriction comes from the interpretation of the model in terms of circuits. A machine running in polynomial time corresponds to circuits for every $n$ of polynomial size. If we now relax the constraint that all these circuits come from some single algorithm, then we get non-uniform polynomial time, which is the same computation with advice depending on $n$ of polynomial size (exercise).

The answer to the first question should obviate the second one. I would just mention that sometimes, instead of probabilistic polynomial-time algorithms, one considers (deterministic) polynomial size circuits.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "So it cannot explicitly contain the n-table for all n." - That seems misleading. It can contain such a table. It is common in cryptography to ask for security against non-uniform adversaries. That means the program can be different for each $n$. A non-uniform adversary can contain such a table. The table can be hardcoded in the code of the program itself (assuming non-uniform adversaries), without the program needing to compute it at runtime. $\endgroup$
    – D.W. ♦
    Commented Aug 8, 2013 at 4:51
  • 1
    $\begingroup$ Paraphrasing your own words, I have anticipated this comment and wrote an entire paragraph about it (the third paragraph). $\endgroup$
    – Yuval Filmus
    Commented Aug 8, 2013 at 4:54
-1
$\begingroup$

  1. Nope. In the standard framework in the cryptographic community, that kind of algorithm is usually not considered probabilistic polynomial-time: if necessary, we tweak the definition to ensure that it's not.

    Technically speaking, in cryptography some folks have suggested we use the sum of the running time plus the size of the program's code as our measure of the time for the attack (you can think of it like this: if the code of the program is $k$ bits, it will take $k$ time steps just to read that code into memory before you start running it). If you hear someone say "running time" in cryptography, they might actually mean that sum. I think I first learned this technical detail from Phil Rogaway, but I have no idea whether he is first.

    If you don't believe me, here's an example citation to the literature: you can look at Bellare et al, The security of the cipher block chaining message authentication code, Journal of Computer and System Sciences. See Section 2.2, Model of computation, where they write:

    We fix some particular Random Access Machine (RAM) as a model of computation. [...] When we speak of A's running time this will include A's actual execution time plus the length of A's description (meaning the length of the RAM program that describes A). This convention eliminates pathologies caused if one can embed arbitrarily large lookup tables in A's description.

    Notice how they anticipated this corner case and chose definitions that avoid it from being problematic. With this definition, everything works out in a reasonable way, and your proposed algorithm (with an exponential-sized constant) is not a probabilistic polynomial-time algorithm.

    Many cryptographers aren't always this careful about their definition of running time. It is very common to be a little sloppy and omit this kind of detail. Often, it doesn't matter. But when we start to talk about exponential-sized constants, this detail does matter, very much, and that's when it is essential to know about this technical detail, if you want to argue over formalisms.

  2. Nope.

By the way, I stand by my answer on this, despite the (unexplained) downvote. Many folks are not aware that others in the research community have already anticipated this kind of subtlety, and few papers make a big deal of it, so I don't blame others for being unaware of the relevant definitions in the cryptographic community.

Improve this answer
$\endgroup$
9
  • $\begingroup$ So, when i want to measure the complexity, do i must think in the way that the algorithm is built from scratch? How about a simple algorithm that compares the input value with hash value of exponential-sized constant? i.e, for given n-bit input string, return 1 if $input == H(1^{2^n})$ where H is polynomial hash function mapping $\{0,1\}^{2^n}\to \{0,1\}^n$ Should i consider this simple algorithm as exponential running time algorithm, in formal point of view? $\endgroup$
    – euna
    Commented Aug 8, 2013 at 4:02
  • $\begingroup$ @euna, like I said, your measure of complexity is the amount of space for the program's code (this includes any constants or constant tables you want to include) plus the time to run the program on your problem instance. So, if your algorithm has an exponential-sized constant, yes, its overall running time will be considered exponential -- in the framework that I'm explaining (which is one that careful authors in cryptography sometimes use). Why add in the size of the program? Exactly because of this sort of example. $\endgroup$
    – D.W. ♦
    Commented Aug 8, 2013 at 4:31
  • $\begingroup$ Thank you for your reply. Is the way of the measure of complexity including program's code consistent with the way of formal view like polynomial Turing machine with random coin? In that, do they explain the complexity of any algorithm in same manner? $\endgroup$
    – euna
    Commented Aug 8, 2013 at 4:44
  • $\begingroup$ Or should i consider polynomial algorithm(polynomial TM) as follows? Not only halts after at most $p(|x|)$, but also the description of the machine is at most $p(|x|)$? Because i only saw the definition of polynomial TM with only first requirement, i'm little confused. $\endgroup$
    – euna
    Commented Aug 8, 2013 at 4:51
  • $\begingroup$ @D.W. The notion of (randomized) polynomial time is exactly the same in complexity theory and in cryptography. If the algorithm is allowed to have advice depending on $n$, then the size of the resulting circuit depends on both the running time and the size of the advice, which is where the "convention" is coming from. The actual convention is to measure circuit size. $\endgroup$
    – Yuval Filmus
    Commented Aug 8, 2013 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.