Timeline for Can one measure the infeasibility of four color proofs?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 17, 2021 at 2:51 | comment | added | markvs | Instead of checking configurations, you need to check the program that checks configurations. I guess, that would take a couple of weeks at most. | |
| Oct 30, 2020 at 14:34 | history | edited | Noah Snyder | CC BY-SA 4.0 |
Updated a dead link, since it's already bumped I also added a paragraph summarizing the discussion in the comments.
|
| Oct 30, 2020 at 14:20 | history | edited | Noah Snyder | CC BY-SA 4.0 |
deleted 9 characters in body
|
| Sep 16, 2013 at 16:46 | comment | added | David E Speyer | THANK YOU. That is a much bigger error in what I am doing than the one I noticed. (The $3$ coloring of edges is equivalent to saying they have pre-eliminated all boundary colorings where two adjacent vertices have the same color, but doing it in terms of edge colorings makes it easy to see that they have done the complete list without dedicating more thinking time to it.) Also, I should be dividing by $12$, not $6$ above. And now my estimate comes back into your $(10^4, 10^6)$ range. | |
| Sep 16, 2013 at 16:42 | comment | added | Noah Snyder | I think it's actually $3^{14}$ and not $4^{14}$ because they translate the question into 3-coloring edges instead of 4-coloring vertices. That saves you a factor of 100. | |
| Sep 16, 2013 at 16:42 | comment | added | David E Speyer | I was simplifying above: The Kempe chains reduce the number of colorings I need to check, but I also need to check that the Kempe chains do eliminate the colorings they are claimed to eliminate. I have not put any serious thought into which is the more significant factor. | |
| Sep 16, 2013 at 16:23 | comment | added | David E Speyer | So I would go with a lower bound more on the order of $10^7$ for the Steinberger proof. RSST has fewer configurations but, more importantly, configurations with smaller boundary. However, what they have to check in each case is more complicated; I haven't figured out whether $C$-reducibility is simple enough to be checked in a minute or not. | |
| Sep 16, 2013 at 16:20 | comment | added | David E Speyer | It surely takes at least second to glance at a 4-coloring and see that it is valid. $10^{11}$ seconds $\approx 3 \times 10^7$ hours. (One also has to check that the list of boundary colorings contains all possible boundary colors, but we can circumvent that by having the computer give them to us in lexicographic order; I can check that one coloring is the lex successor of another in under a second, and then just check $3 \times 10^3$ times that the first and last elements of the list are what they should be.) | |
| Sep 16, 2013 at 16:17 | comment | added | David E Speyer | I am skeptical that reducibility could be checked in $10^6$ person-hours for the Steinberger proof. Reading the definition of $D$-reducibility (Defn. 3.2) I need to check that every $4$-coloring of the boundary of a graph extends to the interior. There are $\approx 3 \times 10^3$ graphs for which I must make this check and most of them have boundaries of size $13$ or $14$ (Table 1). $3 \times 10^3 \times 4^{14}/6 \approx 10^{11}$, where I divide by $6$ because I can permute colorings to fix the colors of two adjacent vertices. (continued) | |
| Sep 16, 2013 at 15:32 | comment | added | Noah Snyder | Yeah, I'd be surprised if the answer isn't something in between $10^4$ hours and $10^6$ hours with current techniques. | |
| Sep 16, 2013 at 15:21 | comment | added | Colin McLarty | This helps answer both of my questions: Graph theorists do have ideas, within an order of magnitude or maybe two, of they mean in calling the problem infeasible without machines. It is much more like $10^4$ hours than $10^8$ years. | |
| Sep 16, 2013 at 15:06 | history | answered | Noah Snyder | CC BY-SA 3.0 |