Decision Problem: Given integers as inputs for $ K$ and $ M$ . Is the sum of $ 2^k$ + $ M$ a $ prime$ ?

## Verifier

`m = int(input('Enter integer for M: ')) sum_of_2**K+M=int(input('enter the sum of 2^k+m: ')) if AKS.sum_of_2**K+M == True: # Powers of 2 can be verified in O(N) time # make sure there is all 0-bits after the 1st ONE-bit # Use difference to verify problem if sum_of_2**K+M - (M) is a power_of_2: OUTPUT Solution Verified `

*The powers of 2 have approximately $ 2^n$ digits. Consider $ 2^k$ where $ K$ = 100000. Compare the amount of digits in $ K$ to the amount of digits in it’s solution!* Also take note that the *powers of 2* have $ 2^n$ bits as its *0-bit Unary* essentially for the exponent $ n$ .

## Question

How would a non-deterministic machine solve this problem in polynomial time?