3 ms·

I don't understand your first bullet point about turing machines. Can you elaborate? > * What do you get if you photocopy a mirror? Black?

by jules 18y ago

RiderOfGiraffes 18y ago
>> What do you get if you photocopy a mirror? > Black? Are you sure? Why? Can you prove it from first principles? It's an interesting challenge - prove that a well-designed photocopier must give a particular result. > I don't understand your first bullet point about turing machines. Can you elaborate? This would be a lot easier if I took considerable time and drew pictures to illustrate. Without, this will be a bit of a slog. I hope it's helpful ... So. It's possible to construct graphs such that a valid three coloring results in behavior equivalent to actions of a logic gate. For example, suppose your colors are called "0", "1" and "#". Take a triangle and color one vertex "#". Label the other vertices "in" and "out". Now you have a "NOT" gate. You can feed the output of one gate into the input of another by identifying the vertices. This allows you to build combinatorial circuits. Now take some instance of any NP problem. (technical terms. A "problem" is a collection of "instances".) A simple example to understand is factoring. Clearly any alleged solution can be checked in polynomial time simply by multiplying the alleged factors and seeing if you get the right answer. Hence the problem is in NP. So given an instance N - a number to factor - construct a TM to multiply two numbers and check if the answer is N. If it is, output "yes". If not, output "no". (There are details about what "output" means for a TM. These can be done.) Now construct the combinatorial circuit that mimics running the TM. Note, it's polynomial in in size because the TM is poynomial in size and runs in polynomial time. (There are details about how that can be done.) Now we have a graph which, if you color the input vertices with a factorization of N, results in the "Yes" vertex getting the color "1". Force the color of the "yes" vertex to be "1" and find a coloring. (How to force a given vertex is a simple technical trick.) If you succeed, then the "input" vertices must hold a valid factorization of N. Thus we have constructed a graph to emulate the TM that multiplies, and run it backwards to make it a factoring machine. This proves that 3-coloring is "harder" than factoring. However, the construction goes through for any NP problem, and hence 3-coloring is NP-hard. Given that 3-coloring is also itself in NP, that shows that 3-coloring is NP-complete. Does that answer your question?
- jules 18y ago
  Yes, I get the idea, but I don't understand how you'd convert an arbitrary TM into a graph. Conversion + coloring is equivalent to running the TM. Coloring runs in finite time, so a conversion algorithm will sometimes not terminate? > Are you sure? No. > Why? As far as I know, photocopiers shine light through the paper on the drum. Electrical charge is eliminated on those places that get light. Black letters block the light, and the toner gets attracted to the charge on the drum where the letters are. Because light can't go through a mirror, it's equivalent to a black sheet of paper. > Can you prove it from first principles? What do you mean by first principles? > prove that a well-designed photocopier must give a particular result. What do you mean by well-designed? I suppose a perfect copier would produce a mirror. A good photocopier can produce either white or black (depending on which side it measures the light). Maybe this is a mathematical question but I don't get it...
  - RiderOfGiraffes 18y ago
    Re photocopier: I don't want to give away the answer and spoil it for those who may want to think about it, but photocopiers do not shine light through paper. When I say "from first principles" I mean - think about the task accomplished by a photocopier, and the general means by which it does that. Deduce from that what must happen when it photocopies a mirror. And when I say "well-designed", early copiers had some undesirable characteristics which have now been eliminated. I can't think of any more to say without giving away the answer. And to the question of the TM: Part of the assumption is that we have an NP problem, hence we have an algorithm (in the technical sense) to verify an alleged solution. By definition that algorithm must run in polynomial space and time. That means the graph only needs to be polynomial in size. More specifically, for each cell on the tape have a vertex for each possible symbol. Arrange logic gates so that exactly one of them will be "1" and the others will be "0". Now also have a set of vertices for the states, and arrange that exactly one will be "1" with the others "0". Make a copy of this, and connect with gates so that the second copy is forced to be the state of the tape and machine after one step. Repeat as many times as there are steps in the algorithm, which is polynomial. In short, we're not converting an arbitrary TM. For a given instance that needs checking the TM is of finite size and runs for finite time, so the graph to color is finite. If it can't be colored the problem has no solution. If it can be colored, the coloring gives you the answer, appearing at its inputs. Please, ask if there's anything still unclear. It's nice to reactivate the associated mental pathways.

I don't understand your first bullet point about turing machines. Can you elaborate? > * What do you get if you photocopy a mirror? Black?

by jules 18y ago

I don't understand your first bullet point about turing machines. Can you elaborate? > * What do you get if you photocopy a mirror? Black?

RiderOfGiraffes 18y ago

>> What do you get if you photocopy a mirror? > Black? Are you sure? Why? Can you prove it from first principles? It's an interesting challenge - prove that a well-designed photocopier must give a particular result. > I don't understand your first bullet point about turing machines. Can you elaborate? This would be a lot easier if I took considerable time and drew pictures to illustrate. Without, this will be a bit of a slog. I hope it's helpful ... So. It's possible to construct graphs such that a valid three coloring results in behavior equivalent to actions of a logic gate. For example, suppose your colors are called "0", "1" and "#". Take a triangle and color one vertex "#". Label the other vertices "in" and "out". Now you have a "NOT" gate. You can feed the output of one gate into the input of another by identifying the vertices. This allows you to build combinatorial circuits. Now take some instance of any NP problem. (technical terms. A "problem" is a collection of "instances".) A simple example to understand is factoring. Clearly any alleged solution can be checked in polynomial time simply by multiplying the alleged factors and seeing if you get the right answer. Hence the problem is in NP. So given an instance N - a number to factor - construct a TM to multiply two numbers and check if the answer is N. If it is, output "yes". If not, output "no". (There are details about what "output" means for a TM. These can be done.) Now construct the combinatorial circuit that mimics running the TM. Note, it's polynomial in in size because the TM is poynomial in size and runs in polynomial time. (There are details about how that can be done.) Now we have a graph which, if you color the input vertices with a factorization of N, results in the "Yes" vertex getting the color "1". Force the color of the "yes" vertex to be "1" and find a coloring. (How to force a given vertex is a simple technical trick.) If you succeed, then the "input" vertices must hold a valid factorization of N. Thus we have constructed a graph to emulate the TM that multiplies, and run it backwards to make it a factoring machine. This proves that 3-coloring is "harder" than factoring. However, the construction goes through for any NP problem, and hence 3-coloring is NP-hard. Given that 3-coloring is also itself in NP, that shows that 3-coloring is NP-complete. Does that answer your question?

jules 18y ago
Yes, I get the idea, but I don't understand how you'd convert an arbitrary TM into a graph. Conversion + coloring is equivalent to running the TM. Coloring runs in finite time, so a conversion algorithm will sometimes not terminate? > Are you sure? No. > Why? As far as I know, photocopiers shine light through the paper on the drum. Electrical charge is eliminated on those places that get light. Black letters block the light, and the toner gets attracted to the charge on the drum where the letters are. Because light can't go through a mirror, it's equivalent to a black sheet of paper. > Can you prove it from first principles? What do you mean by first principles? > prove that a well-designed photocopier must give a particular result. What do you mean by well-designed? I suppose a perfect copier would produce a mirror. A good photocopier can produce either white or black (depending on which side it measures the light). Maybe this is a mathematical question but I don't get it...
- RiderOfGiraffes 18y ago
  Re photocopier: I don't want to give away the answer and spoil it for those who may want to think about it, but photocopiers do not shine light through paper. When I say "from first principles" I mean - think about the task accomplished by a photocopier, and the general means by which it does that. Deduce from that what must happen when it photocopies a mirror. And when I say "well-designed", early copiers had some undesirable characteristics which have now been eliminated. I can't think of any more to say without giving away the answer. And to the question of the TM: Part of the assumption is that we have an NP problem, hence we have an algorithm (in the technical sense) to verify an alleged solution. By definition that algorithm must run in polynomial space and time. That means the graph only needs to be polynomial in size. More specifically, for each cell on the tape have a vertex for each possible symbol. Arrange logic gates so that exactly one of them will be "1" and the others will be "0". Now also have a set of vertices for the states, and arrange that exactly one will be "1" with the others "0". Make a copy of this, and connect with gates so that the second copy is forced to be the state of the tape and machine after one step. Repeat as many times as there are steps in the algorithm, which is polynomial. In short, we're not converting an arbitrary TM. For a given instance that needs checking the TM is of finite size and runs for finite time, so the graph to color is finite. If it can't be colored the problem has no solution. If it can be colored, the coloring gives you the answer, appearing at its inputs. Please, ask if there's anything still unclear. It's nice to reactivate the associated mental pathways.