<p>Say we want to capture the notion that an efficiently samplable distribution <span class="math-container">$D(1^n)$</span> is hard with respect to some boolean function <span class="math-container">$f$</span> for a decision problem or some efficient relation <span class="math-container">$R$</span> for a search problem. Usually we will require that every efficient algorithm <span class="math-container">$A$</span> fails on large enough <span class="math-container">$n$</span>'s, where failure and efficiency are defined according to the context. For example see <a href="https://en.wikipedia.org/wiki/One-way_function#Theoretical_definition" rel="nofollow noreferrer">One-way function: Theoretical definition</a>.</p>
<p>Let us consider the contradiction that <span class="math-container">$A$</span> breaks the assumption, then it succeeds on infinitely many <span class="math-container">$n$</span>'s. My question is, can we say anything about these <span class="math-container">$n$</span>'s for common hardness definitions?<br />
More specifically, if the set of successful <span class="math-container">$n$</span>'s is something like <span class="math-container">$\{n \geq 64\}_{n\in\mathbb{N}},\{3n\}_{n\in\mathbb{N}},\{n^8\}_{n\in\mathbb{N}}$</span>, or even <span class="math-container">$\{2^n\}_{n\in\mathbb{N}}$</span>, then I can see that in some sense the hardness assumption was broken. However, what if the set of successful <span class="math-container">$n$</span>'s is something like <span class="math-container">$\{\text{Ackermann}(n,n)\}_{n\in\mathbb{N}}$</span>? Is there any work that addresses this issue?</p>
<p>In particular, in the four simple cases above we can always define <span class="math-container">$D'(1^n)\gets D(1^1),D(1^2),\dots,D(1^n)$</span> and ask to solve all of them, then we must hit a hard <span class="math-container">$n$</span> 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.</p>

CC BY-SA 4.0
2022-12-27T06:05:44.547Z
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.
D.W.
CC BY-SA 4.0
2022-12-27T19:14:05.167Z
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.
usul
CC BY-SA 4.0
2022-12-28T08:58:58.930Z
@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.
Nathan
CC BY-SA 4.0
2022-12-28T09:04:11.043Z
@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?
Nathan
CC BY-SA 4.0
2022-12-28T14:46:00.327Z
It depends if you are thinking about computational complexity or cryptography - your added link indicates cryptography, so I agree.
usul
CC BY-SA 4.0
2022-12-28T17:51:38.567Z
Adding a link to say "for example one-way functions" does not answer my questions.  I think that by trying to ask in such generality, you're ending up with a question that is so vague it's hard to tell what you are asking.  I recommend that you pick a special case where you *can* define the question precisely, and ask about that.  If you get an answer to that and don't see how to generalize it, you can later ask another question that is a bit more general.  "Can we say the problem is hard?" - it depends what you mean by hard, and what definition of hard you are using, and what the context is.
D.W.
<cc.complexity-theory><cr.crypto-security><definitions>
Restrictions on set of infinitely many n's for which an algorithm breaks distributional hardness
Nathan
# Restrictions on set of infinitely many n's for which an algorithm breaks distributional hardness

(Asked by: username_0 on 2022-12-25)

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](https://en.wikipedia.org/wiki/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.

**Tags:** cc.complexity-theory, cr.crypto-security, definitions

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: @username_1 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.  
> **username_0**: @username_2 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?  
> **username_2**: It depends if you are thinking about computational complexity or cryptography - your added link indicates cryptography, so I agree.  
> **username_1**: Adding a link to say "for example one-way functions" does not answer my questions.  I think that by trying to ask in such generality, you're ending up with a question that is so vague it's hard to tell what you are asking.  I recommend that you pick a special case where you *can* define the question precisely, and ask about that.  If you get an answer to that and don't see how to generalize it, you can later ask another question that is a bit more general.  "Can we say the problem is hard?" - it depends what you mean by hard, and what definition of hard you are using, and what the context is.  

---

## 0 answers

