I can verify solutions to my problem in polynomial time, how would a non-deterministic algorithm arrive to a solution if it always takes $2^n$ bits? 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?
As I see it, this decision problem is obviously in P. Therefore, there is nothing for non-deterministic Turing machine to guess. Non-deterministic Turing machine would call polynomial-time verifier for a given problem instance and the problem would be solved in polynomial time.