Say we want to capture the notion that an efficiently samplable distribution $D(1^n)$ is hard with respect to some boolean function $f$ for a decision problem or some efficient relation $R$ for a search problem. Usually we will require that every efficient algorithm $A$ fails on large enough $n$'s, where failure and efficiency are defined according to the context. For example see One-way function: Theoretical definition.

Let us consider the contradiction that $A$ breaks the assumption, then it succeeds on infinitely many $n$'s. My question is, can we say anything about these $n$'s for common hardness definitions?
More specifically, if the set of successful $n$'s is something like $\{n \geq 64\}_{n\in\mathbb{N}},\{3n\}_{n\in\mathbb{N}},\{n^8\}_{n\in\mathbb{N}}$, or even $\{2^n\}_{n\in\mathbb{N}}$, then I can see that in some sense the hardness assumption was broken. However, what if the set of successful $n$'s is something like $\{\text{Ackermann}(n,n)\}_{n\in\mathbb{N}}$? Is there any work that addresses this issue?

In particular, in the four simple cases above we can always define $D'(1^n)\gets D(1^1),D(1^2),\dots,D(1^n)$ and ask to solve all of them, then we must hit a hard $n$ of relatable size so it seems the choice of set doesn't matter that much, but this approach no longer works for the Ackermann function.

  • $\begingroup$ It's not clear what you mean by saying that a distribution is hard, or hard with respect to $f$. It's not clear what you mean by "fails" or "breaks the assumption". Please provide a self-contained definition for all terms. What do you mean by "addresses this issue"? It's hard to tell what you are looking for. Perhaps you are interested in non-uniform complexity as is typically used in cryptography, or in concrete security, but it's hard to tell. I encourage you to edit your question to make it clearer what you are asking. $\endgroup$
    – D.W.
    Dec 27, 2022 at 6:05
  • $\begingroup$ I think I disagree with the premise. I'd say a problem is hard if every algorithm is incorrect on infinitely many inputs, and the negation would be an algorithm exists that is correct for all large enough inputs. $\endgroup$
    – usul
    Dec 27, 2022 at 19:14
  • $\begingroup$ @D.W. I linked the definition for OWFs for concreteness, although I think the question could be seen more generally, for example we may not care about being able to sample instances together with a solution. You are correct that my question is not well defined, currently this issue is preventing me from proving something and ideally I'd like to see an explanation why we can assume w.l.o.g. that we are not in the case with the Ackermann function, but I don't think it's true so I was simply asking if this issue has already been looked at by some prior works. $\endgroup$
    – Nathan
    Dec 28, 2022 at 8:58
  • $\begingroup$ @usul Well I did not come up with these definitions but I think the idea is this: If you can solve the problem for large enough n's then it's easy, if you cannot solve it for large enough n's then it's hard. If for example you can solve a problem on even n's but not on odd n's then it's neither easy nor hard, it's something in between. But even if we use your definition we can still ask about the case where A is only incorrect on inputs of size {Ackermann(n,n)}, can you really say the problem is hard in this case? $\endgroup$
    – Nathan
    Dec 28, 2022 at 9:04
  • $\begingroup$ It depends if you are thinking about computational complexity or cryptography - your added link indicates cryptography, so I agree. $\endgroup$
    – usul
    Dec 28, 2022 at 14:46


Your Answer

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