Two cyborgs walk into your home, both claiming to be oracles for the graph 3- co
ID: 3580892 • Letter: T
Question
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.
Explanation / Answer
It is possible to expose the impostor within time polynomial in the size of that instance by using the oracle to output coloring. The right one gives the valid coloring.
Proof:
Construct three nodes of 3 different colors like red, yellow, blue and connect these three nodes as a triangle in the graph.
There exists a method to force a node so that it can have a certain color. The color of the nodes can be guessed because if it is required to force a node to have a color then the other two nodes (in this case) can be connected to it.
Algorithm: To expose the impostor within the polynomial time in the size of that instance, the algorithm is as follows:
if (there exists uncolored node)
{
color it red
else if (colored graph is not 3 colorable)
{
color it yellow
else if (colored graph is not 3 colorable)
{
color it blue
else if (colored graph is not 3 colorable)
{
print (“The impostor is exposed”)
}
}
}
}
print (“You are a true oracle”)
This algorithm takes polynomial time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.