1. Is NP countable?
Please show your proof. Thank you for your time.
2.Two cyborgs walk into your home, both claiming to be oracles for the graph 3-colorability decision problem. They both always give a yes/no answer in constant time for any instance, and are each self-consistent (i.e. each always gives the same answer for the same instance). However, one is a true oracle and the other is a shameless impostor, and you have a large instance of 3-colorability upon which they disagree.
Prove whether it is possible to expose the impostor within time polynomial in the size of that instance.