2
$\begingroup$

I read online that this problem is in P:

Problem = {a^n, where n is a primary number}

I can't find any algorithm that decides if a word w in {a}* is in Problem, can someone help me because I'm not really convinced that this problem can be solved in polynomial time.

$\endgroup$
2
$\begingroup$

Hint: does being in P have something to do with the length of the input?

$\endgroup$
1
$\begingroup$

This might help you: The AKS primality test is in P.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy