Ackermann Decision Problem

I have been studying the Ackermann function, specifically the two-argument Ackermann–Péter version.

With the Ackermann function, I developed a problem I call the "Ackermann Decision Problem"

Given non-negative integers, x and y, does A(x,x) = y?

The naive solution to verify the Ackermann Decision Problem would be to compute the Ackermann Function. From my research, I seem to be unable to find a way to compute the Ackermann Function in polynomial time.

Is this problem in NP?

Is the time complexity for verifying and solving the Ackermann Decision Problem the same?

• You only need to compute the Ackermann function in time polynomial on the length of the answer. It seems to me that you can do this using Knuth-arrow definitions: en.wikipedia.org/wiki/Ackermann_function#Definition Commented Mar 22, 2023 at 20:20
• And you don’t have to compute it, only show that it is larger than y in that time. You stop as soon as you know A(x) is too large. Commented Mar 25, 2023 at 12:53

No, you don’t need to compute the Ackerman function to verify this at all.

The problem is trivial for x <= 3. And for x >= 4, if you can write down y, then the answer is “no”.

More serious, if you actually wrote down say y ≈ A(4), you can solve it easily in linear time in the size of y. If calculating A(4) takes more time than that then you know it is greater than y and stop calculating.

PS. This is a question/answer site, not a free proof writing service.

• I cannot see how "you don’t need to compute the Ackerman function to verify this at all". I don't see any relevance of $A(4)$ to this question on computational complexity, which is about the asymptotic behavior when the length of input goes to infinity. $A(4)$ is just one number. Commented Mar 23, 2023 at 15:05
• Well, go through my post and find what becomes wrong when you replace A(4) with A(5). The point stands that if you can write y then it isn't equal to A(4). And in a hypothetical world where you wrote down a number y huge enough that it might be A(k) for some k ≥ 4, deciding that A(k) = y takes only linear time in the size of y. Commented Mar 23, 2023 at 16:29
• While your conclusion might be right, where is the justification? This answer does not use any property of Ackermann function except that $A(x,x)$ is large relative to $x$. Have you proved linear time is enough? Commented Mar 23, 2023 at 16:46
• How would you justify for example if I replace $A(x,x)$ with $\sqrt{A(x,x)}$? Or $A(x,x)/A(x-1,x-1)$? Commented Mar 23, 2023 at 16:52
• Once again, I am asking for a proof. I am not saying at all that I don't believe your conclusion that linear time is enough. Commented Mar 24, 2023 at 1:56