10 ms·

It is interesting because it is easy to understand the problem quickly -- we've all seen maps. Additionally, for graph theory, the solution is pretty accessibl

It is interesting because it is easy to understand the problem quickly -- we've all seen maps. Additionally, for graph theory, the solution is pretty accessible. I took just an introductory course in graph theory so I only got to see this famous problem and a few others. I would think that this crowd would find a list of other famous problems from your field quite interesting.

RiderOfGiraffes 18y ago
the solution is pretty accessible. I don't think that's true. I think you'll find the proof that discharging gives you what you want is pretty impenetrable. And this is a review of a survey paper that doesn't actually give the details. I guess in this case I know too much about the topic to be able to assess whether it will be interesting to a generic hacker. I think it's pretty content-free. That's probably also the difference between me and a good science writer. Anything I read about something I know seems to be complete content-free fluff. I've tried, but I don't think I'll ever be able to write anything for general consumption. However, here are a couple of results and/or odd questions: * Given a Turing Machine one can construct a graph such that 3-coloring the graph is equivalent to running the Turing machine. >> Since 3-coloring doesn't have a "direction", that means you can effectively run the TM backwards. >>> That is a direct proof that 3-coloring is NP-complete. * The set of reals is bigger than the set of integers * One cannot decide from the axioms of set theory whether there is a set of reals that is bigger than the set of integers, but smaller than the set of reals. * pi is very closely approximated by 355/113 * Define the sequence k(1)=0, k(2)=2, k(3)=3, k(n)=k(n-2)+k(n-3), and for n>1 ask: Does n divide k(n)? The answer is always "Yes" if n is prime, and almost always "No" if n is composite. Challenge: find the first 5 cases where it gives the "wrong" answer. Finally: * What do you get if you photocopy a mirror?
- emmett 18y ago
  I found this post interesting. I'd subscribe to your blog if the posts were about things like this.
  - RiderOfGiraffes 18y ago
    Oh. Gosh. <fx: blush> I might have to think about getting a blog, then ...
- 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?
- rw 18y ago
  What's your definition of a "generic hacker"?
  - RiderOfGiraffes 18y ago
    Good question - not sure I can answer ... I've known lots of people who program/hack but who do so because they want results from computers, not because they are producing programs as product. They are people using computers as tools, and I would not class them as generic hackers. I guess I meant people who program to produce programs as the main goal, as opposed to producing programs to perform an analysis and get results. For example, I wrote programs for my Ph.D. and for the research positions I held afterwards. I wanted the answers from the computations. I didn't want the programs. These days I write programs to analyse data (of a specific and esoteric nature) and I manage people who write programs that form part of a product. They are generic hackers. I'm not. This isn't, in my usage, a derogatory terms. I'm not implying that programmers are interchangable parts. they're not. Some of my team are gifted all-rounders. They choose, however, to write programs-as-products as their means of earning a living. Most, but not all, also write programs for fun. They're also not limited to web programming, or database programming, or spreadsheet programming, or any other domain specific work. They program generally, and can turn their hand to any domain, always with competent and workmanlike results, although not always as well as specialists from the area. Does that make it clearer? Does it actually matter? I probably used the term to refer to people who can program generally, and in a wide variety of domains, as opposed to those that have limited experience, knowledge and ability. I'm no longer sure though, and don't think it really matters. "Closed Mouths Gather No Feet." Perhaps I should've shut up ages ago ...
- jibiki 18y ago
  > Define the sequence k(1)=0, k(2)=2, k(3)=3, k(n)=k(n-2)+k(n-3), and for n>1 ask: Does n divide k(n)? The answer is always "Yes" if n is prime, and almost always "No" if n is composite. I can see why this is true for primes where x^3 + x^2 - 1 = 0 has a solution mod p (because then you can find a closed form for the recurrence mod p.) But I have no idea how to do it in general (it looks like a generalization of Fermat's little theorem.)

RiderOfGiraffes 18y ago

the solution is pretty accessible. I don't think that's true. I think you'll find the proof that discharging gives you what you want is pretty impenetrable. And this is a review of a survey paper that doesn't actually give the details. I guess in this case I know too much about the topic to be able to assess whether it will be interesting to a generic hacker. I think it's pretty content-free. That's probably also the difference between me and a good science writer. Anything I read about something I know seems to be complete content-free fluff. I've tried, but I don't think I'll ever be able to write anything for general consumption. However, here are a couple of results and/or odd questions: * Given a Turing Machine one can construct a graph such that 3-coloring the graph is equivalent to running the Turing machine. >> Since 3-coloring doesn't have a "direction", that means you can effectively run the TM backwards. >>> That is a direct proof that 3-coloring is NP-complete. * The set of reals is bigger than the set of integers * One cannot decide from the axioms of set theory whether there is a set of reals that is bigger than the set of integers, but smaller than the set of reals. * pi is very closely approximated by 355/113 * Define the sequence k(1)=0, k(2)=2, k(3)=3, k(n)=k(n-2)+k(n-3), and for n>1 ask: Does n divide k(n)? The answer is always "Yes" if n is prime, and almost always "No" if n is composite. Challenge: find the first 5 cases where it gives the "wrong" answer. Finally: * What do you get if you photocopy a mirror?

emmett 18y ago
I found this post interesting. I'd subscribe to your blog if the posts were about things like this.
- RiderOfGiraffes 18y ago
  Oh. Gosh. <fx: blush> I might have to think about getting a blog, then ...
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?
rw 18y ago
What's your definition of a "generic hacker"?
- RiderOfGiraffes 18y ago
  Good question - not sure I can answer ... I've known lots of people who program/hack but who do so because they want results from computers, not because they are producing programs as product. They are people using computers as tools, and I would not class them as generic hackers. I guess I meant people who program to produce programs as the main goal, as opposed to producing programs to perform an analysis and get results. For example, I wrote programs for my Ph.D. and for the research positions I held afterwards. I wanted the answers from the computations. I didn't want the programs. These days I write programs to analyse data (of a specific and esoteric nature) and I manage people who write programs that form part of a product. They are generic hackers. I'm not. This isn't, in my usage, a derogatory terms. I'm not implying that programmers are interchangable parts. they're not. Some of my team are gifted all-rounders. They choose, however, to write programs-as-products as their means of earning a living. Most, but not all, also write programs for fun. They're also not limited to web programming, or database programming, or spreadsheet programming, or any other domain specific work. They program generally, and can turn their hand to any domain, always with competent and workmanlike results, although not always as well as specialists from the area. Does that make it clearer? Does it actually matter? I probably used the term to refer to people who can program generally, and in a wide variety of domains, as opposed to those that have limited experience, knowledge and ability. I'm no longer sure though, and don't think it really matters. "Closed Mouths Gather No Feet." Perhaps I should've shut up ages ago ...
jibiki 18y ago
> Define the sequence k(1)=0, k(2)=2, k(3)=3, k(n)=k(n-2)+k(n-3), and for n>1 ask: Does n divide k(n)? The answer is always "Yes" if n is prime, and almost always "No" if n is composite. I can see why this is true for primes where x^3 + x^2 - 1 = 0 has a solution mod p (because then you can find a closed form for the recurrence mod p.) But I have no idea how to do it in general (it looks like a generalization of Fermat's little theorem.)