0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Dmitry
    Commented Mar 22, 2023 at 20:20
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Mar 25, 2023 at 12:53

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Mar 23, 2023 at 15:05
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Mar 23, 2023 at 16:29
  • $\begingroup$ 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? $\endgroup$
    – John L.
    Commented Mar 23, 2023 at 16:46
  • 1
    $\begingroup$ 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)$? $\endgroup$
    – John L.
    Commented Mar 23, 2023 at 16:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Mar 24, 2023 at 1:56

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.