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?
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.