Really helpful video! Just one question, Since the problem is given an arbitrary Graph how do we know its CNF formula? Usually, a graph is a set of nodes so would we need to explicitly say that Graph G is a representation of a formula?
When we Karp reduce from some problem X to some problem Y we need to be able to map *every* input for X to *some* input for Y. But the reverse does not have to be true! So there may be inputs for Y that we would never generate with our reduction. That is completely fine. In technical terms, the function that is our reduction does not have to be surjective. Consider the following toy example: Let X be the problem of deciding whether a given graph has more than five edges (an easy problem to solve, I know). Let Y be the problem of deciding whether a number is odd. One valid reduction would be the following: Check whether the graph has more than five edges. If the answer is yes, output 85. If the answer is no, output 42. This is a valid reduction despite the fact that there are many numbers that we would never produce. The important part is only that we output an odd number, if the graph has more than five edges and an even number otherwise. This is a silly example of course because the problem X is already contained in P and so there is hardly a need to construct such a reduction in the first place. However, technically, there is nothing wrong with our reduction here and it demonstrates that we do not need to be able to produce all possible inputs for problem Y.
in this case the problem is that Xi and ~Xi have the same color, as this would not be consistent. In the case of a 3SAT problem formula, we must have at least one of the literals have the true value, therefore, I believe that nothing prevents it from having two true values as long as they are not opposite literals. My english is very bad, sorry
what if we have 3 literals in each of the 3 clause, do we still assign a single buffer too?
Superb! Made it really click!
Really helpful video! Just one question, Since the problem is given an arbitrary Graph how do we know its CNF formula? Usually, a graph is a set of nodes so would we need to explicitly say that Graph G is a representation of a formula?
When we Karp reduce from some problem X to some problem Y we need to be able to map *every* input for X to *some* input for Y. But the reverse does not have to be true! So there may be inputs for Y that we would never generate with our reduction. That is completely fine. In technical terms, the function that is our reduction does not have to be surjective.
Consider the following toy example: Let X be the problem of deciding whether a given graph has more than five edges (an easy problem to solve, I know). Let Y be the problem of deciding whether a number is odd. One valid reduction would be the following:
Check whether the graph has more than five edges. If the answer is yes, output 85. If the answer is no, output 42. This is a valid reduction despite the fact that there are many numbers that we would never produce. The important part is only that we output an odd number, if the graph has more than five edges and an even number otherwise.
This is a silly example of course because the problem X is already contained in P and so there is hardly a need to construct such a reduction in the first place. However, technically, there is nothing wrong with our reduction here and it demonstrates that we do not need to be able to produce all possible inputs for problem Y.
Which software are you using?
Why can't x1 and ~x2 both be green? Or red?
in this case the problem is that Xi and ~Xi have the same color, as this would not be consistent. In the case of a 3SAT problem formula, we must have at least one of the literals have the true value, therefore, I believe that nothing prevents it from having two true values as long as they are not opposite literals. My english is very bad, sorry
Really helpful thanks!