3 ms·
>> 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 tha
by 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 agoYes, 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 agoRe 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.
- jules 18y ago> prove that a well-designed photocopier must give a particular result. Yes, that was stupid of me (you can copy books too after all). When you place an object on a photocopier its goal is to make an object that has the same optical properties as the original. So the copier will scan it with light to determine how it reacts. Then it will produce an object that reacts in the same way. So the result should also be a mirror. > Please, ask if there's anything still unclear. It's nice to reactivate the associated mental pathways. The numbers A and B that are the input to the algorithm that checks if they multiply to N can't be arbitrary size, because then we'd need an infinite graph to represent them. So it's important that 1<A<N and 1<B<N. What you're saying about the TM is that if you have a TM and a number K you can create a graph that will execute the first K steps of the TM. And because checking is polynomial in N you can make K big enough to execute the algorithm, but still polynomial in N. I don't understand exactly how you'd connect state+tape K with state+tape K+1 so that state K+1 is forced to be the right state. You'd need a giant switch statement of the program counter and then connect the states and tape cells to the next state+tape through the results of the giant switch. But I'm not sure why the resulting graph is still polynomial in N.