[b-side]

I always wondered how the following setup does not prove that NP != P so please chime in.

Finding the correct N-bit long (binary) number (that someone is thinking of, they only reply yes or no to a guess). Verifying if the number is correct can be done in Polynomial time yet finding the correct number can only be achieved by trying (brute force) all the 2^N possibilities?

[teraflop]

For P vs. NP to apply, you would have to be given a Turing machine (or equivalent program) that could verify a guess in polynomial time, without having to ask somebody.

But how do you know that Turing machine couldn't be somehow reverse-engineered to find the number without trying every possibility? You don't know, you're just assuming it. Proving that assumption is the entire point of the problem.

[moritzwarhier]

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.

[supernewton]

You don't get to have "hidden information". The code used to respond "yes" or "no" to the guess would be part of the problem input. But, we currently can't prove there doesn't exist some algorithm that can examine that code and figure out what the "yes" input is faster than brute forcing all inputs.

[planede]

Because that's not the framework where N and NP applies. There is no notion of black boxes outside of the algorithm.

[baraah]

From watching the linked video, and going by the given informal definition for NP-Problems "hard to compute, easy to verify" I think of it this way: You can not compute the secret number efficiently, only the keeper of the secret knows it. So the number is indeed hard to compute. But can you easily verify a solution? Sure you can ask the keeper and he can tell you the answer, but then you didn't verify it yourself. If you count on the secret keepers cooperation he could also just tell you the number, making it easy to compute.

[adgjlsfhk1]

there is an O(n) Turing machine that guesses only the correct binary number. you just don't know which.