Is it allowed to do a binary search with an oracle when proving NP-completeness?

In https://cs.stackexchange.com/a/45524/28999, they do a binary search using an oracle for an NP-Complete problem. They show that the original problem can be reduced to that NP-Complete problem, implying that the original problem is in NP.

Why is that allowed? Why are you allowed to continue after the oracle returns false? Doesn't this defeat the whole idea of NPC versus co-NPC? You could then simply use an oracle for a NP-complete problem to show that NPC = co-NPC?

I would think that the whole reduction is wrong and that the original problem is probably not in NP. Or aren't they implying that?

Well, nowhere does the answer claim the reduction "implies that the original problem is in NP". So, that explains your confusion. You read something into the answer that isn't actually there.

Also, the answer says "Cook reduction". This was a heads-up about the fact that it's not the Karp-style reduction you might be used to. You might like to learn about the difference between a Cook reduction vs a Karp reduction. Read https://en.wikipedia.org/wiki/Turing_reduction. As you suspected, a Karp reduction is part of what is used in the definition of NP-completeness, but this answer isn't trying to prove NP-completeness, so the Cook reduction is "allowed".

StackExchange Computer Science Q#45635, answer score: 5