| NP means, a solution can be found in polynomial time with a hypothetical non-deterministic Turing machine. If your problem statement includes the number to be guessed, it's trivial and solvable in linear time without non-determinism. If it does not include the number to be guessed, then the process of "verifying the solution" has no access to this info by definition too, and it is not possible to verify the solution at all!? Apart from that, the verifiability of a solution in polynomial time on a deterministic Turing machine is a necessary consequence of a problem being in NP, but the reverse direction does not apply without additional conditions, IIRC. If you want to say anything interesting about related problems in regard to complexity theory, you'll have to introduce an "oracle". As far as my knowledge goes, even this doesn't make the problem of "guess an unknown number" without further qualification more interesting. Maybe it would be a good exercise to apply these ideas to binary search for an unknown number, with the answer (greater, smaller, correct) as an oracle. Of course the number must be computable, which doesn't preclude it from being transcendental. Another interesting rabbit hole :) It looks as if you exclude any numbers with an infinite decimal representation by allowing an oracle that says "yes" or "no" to a guess — but of course numbers can also be defined using different means, e.g. convergent sum series etc — and we both know that Pi is finite, right? A formula that can calculate Pi to an arbitrary precision is a finite and complete representation of Pi, just not as a sequence of digits. Digging further into this would lead away from CS and into Maths, particularly there are old and new discussions about the "existance" of transcendental numbers (irrational would suffice, too). This is a part of our shared scientific basics, at least in any math-adjacent field. Googling "Nicolas Bourbaki" is at least as interesting as the complexity theory zoo :) But probably I'm going over my head here since I don't know much about complexity theory apart from faint CS course memories about Cook's theorem. |