patternMajor
Assuming P = NP, how would one solve the graph coloring problem in polynomial time?
Viewed 0 times
assumingproblemthecoloringgraphpolynomialtimewouldonesolve
Problem
Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?
Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for some $k$ satisfying the property that $(u,v) \in E$ implies $\chi(u)\ne\chi(v)$ so as to minimize the fewest number $k$ of “colors”.
Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for some $k$ satisfying the property that $(u,v) \in E$ implies $\chi(u)\ne\chi(v)$ so as to minimize the fewest number $k$ of “colors”.
Solution
There are two cases:
-
$P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded middle. In this case, we have no idea what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we know that if it doesn't exist, we can derive a contradiction. So a proof of this form is pretty useless for solving problems quickly.
-
$P = NP$ constructively. In this case, we have a polynomial time algorithm for some $NP$-hard problem, let's say $L$. If $L$ is NP-hard, then it must solve some other NP-hard problem in polynomial time (i.e. it reduces from that problem). That problem, in turn, either reduces from another problem, or has a direct reduction from every problem in $NP$. We keep following the trail of reductions until we get to one with a direct proof (probably 3SAT).
By composing these reductions, we get an algorithm that solves 3SAT in polynomial time (because each reduction only makes a polynomial number of calls to the previous algorithm, and our starting algorithm for $L$ runs in polynomial time.
We then plug that algorithm into the reduction from Cook-Levin theorem, which gives us a way to simulate any algorithm running in Polynomial time with a polynomial number of calls to a 3SAT solver. Again, a polynomial number of calls to a polynomial-time algorithm runs in polynomial time.
Finally, there is a simple non-deterministic algorithm that solves Graph-coloring in polynomial time: just guess a coloring and check if it's valid. So we use Cook-Levin to simulate this algorithm in polynomial time.
As you can imagine, each time we have to compose a reduction, the degree of our polynomial is going to get higher and higher. So it's entirely possible that $P = NP$ but graph colouring can only be solved in, say, $O(n^{100000000000000})$ time. This is still polynomial time, but it really doesn't buy us much in terms of practically solving problems.
-
$P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded middle. In this case, we have no idea what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we know that if it doesn't exist, we can derive a contradiction. So a proof of this form is pretty useless for solving problems quickly.
-
$P = NP$ constructively. In this case, we have a polynomial time algorithm for some $NP$-hard problem, let's say $L$. If $L$ is NP-hard, then it must solve some other NP-hard problem in polynomial time (i.e. it reduces from that problem). That problem, in turn, either reduces from another problem, or has a direct reduction from every problem in $NP$. We keep following the trail of reductions until we get to one with a direct proof (probably 3SAT).
By composing these reductions, we get an algorithm that solves 3SAT in polynomial time (because each reduction only makes a polynomial number of calls to the previous algorithm, and our starting algorithm for $L$ runs in polynomial time.
We then plug that algorithm into the reduction from Cook-Levin theorem, which gives us a way to simulate any algorithm running in Polynomial time with a polynomial number of calls to a 3SAT solver. Again, a polynomial number of calls to a polynomial-time algorithm runs in polynomial time.
Finally, there is a simple non-deterministic algorithm that solves Graph-coloring in polynomial time: just guess a coloring and check if it's valid. So we use Cook-Levin to simulate this algorithm in polynomial time.
As you can imagine, each time we have to compose a reduction, the degree of our polynomial is going to get higher and higher. So it's entirely possible that $P = NP$ but graph colouring can only be solved in, say, $O(n^{100000000000000})$ time. This is still polynomial time, but it really doesn't buy us much in terms of practically solving problems.
Context
StackExchange Computer Science Q#121710, answer score: 42
Revisions (0)
No revisions yet.