14 ms·
200 terabyte proof demonstrates the potential of brute force math
- modalduality 9y agoDoes anyone know what the proof actually proves, and how the reduction was formulated?
- curiousgal 9y agoTheorem — The set {1, . . . , 7824} can be partitioned into two parts, such that no part contains a Pythagorean triple, while this is impossible for {1, . . . , 7825}. https://arxiv.org/pdf/1605.00723.pdf https://arxiv.org/pdf/1605.00723.pdf
- jordigh 9y agoYeah, when I saw "200 terabytes" I thought it was going to be about the Erdős discrepancy problem, since that's been making the rounds in the popular press, but turns out that only required 13 gigabytes for the 2010 proof. I'm glad that Terry seems to have found a different proof. I attended a discussion of it during last week's Mathematical Congress of the Americas here in Mtl, and I think they were saying that Terry's proof seems correct.
- rocqua 9y agoAbstract: ------------------------- Recent progress in automated reasoning and supercomputing gives rise to a new era of brute force. The game changer is “SAT,” a disruptive, brute-reasoning technology in industry and science. We illustrate its strength and potential via the proof of the Boolean Pythagorean Triples Problem, a long-standing open problem in Ramsey Theory. This 200TB proof has been constructed completely automatically—paradoxically, in an ingenious way. We welcome these bold new proofs emerging on the horizon, beyond human understanding— both mathematics and industry need them.
- Xeoncross 9y ago> This 200TB proof How do you verify a 200TB proof?
- falcolas 9y agoGenerate another proof (using a different method; Coq?) of the proof? That's all I can think of.
- justinpombrio 9y agoWith software.
- johncolanduoni 9y agoUsually by trusting/auditing/verifying the program you use to verify the proof. Which will be much easier to do by hand than 200TB worth of data.
- slaymaker1907 9y agoNot only do you need to verify the code, you also need to generate the proof multiple times since there is a significant possibility of hardware error with that large of a dataset.
- Confusion 9y agoYou have hecksums and other internal consistency checks to deal with those.
- AnimalMuppet 9y agoThey won't actually help. With hecksums, you're darned if you do, and darned if you don't. ;-)
- noir_lord 9y ago..and then rewrite it again via a clean room approach and run that one and see if they tally. Preferably on different hardware.
- danharaj 9y agoThe article: https://cacm.acm.org/magazines/2017/8/219606-the-science-of-brute-force/fulltext https://cacm.acm.org/magazines/2017/8/219606-the-science-of-... Note that most people believe that co-NP /= NP, which implies that an unsatisfiability proof via SAT solving in general won't be efficiently verifiable.
- opportune 9y agoFrom a technical standpoint, this is a terribly written article. First, giving an example of solving an algebraic equation using brute force is misleading, because you can't enumerate all values of a real number. Second, the risks of secrutity regarding brute force computing having nothing to do with SAT. Also, their description of SAT is inaccurate. It's not new, and it was actually one of the first formal problems studied in computer science. Also, the original, linked paper notes that it is not brute-force computing that is itself the breakthrough, but the addition of heuristics in SAT solvers that make brute-forcing feasible.
- bassman9000 9y agoI stopped reading after this This is thanks to a newish technology called Satisfiability (SAT) solving, which is a method of generating proofs in propositional logic. SAT3 was old when I was in college. And it's not to generate proofs.
- slaymaker1907 9y agoEven for integral/rational solutions, the problem is still Turing complete since there may be no solution at all.
- opportune 9y agoTrue, countability doesn't change the problem. Solving a mathematical equation is just a bad way in general to explain what a brute force solver does. Much better to use an example such as a crossword puzzle or sudoku
- legulere 9y agoThis article is about SMT-solvers, which are used in formal verification, which can be about security. SMT solvers are kind of newish: https://excape.cis.upenn.edu/documents/ClarkBarrettSlides.pdf https://excape.cis.upenn.edu/documents/ClarkBarrettSlides.pd...
- opportune 9y ago
- Havoc 9y agoI suspect the average mathematician won't consider that "elegant".
- vernie 9y agoSure, but so what?
- Koshkin 9y agoIt is unlikely that such proof can be considered a contribution to mathematics. Finding "elegant" proofs (and not just "facts"), building conceptual frameworks in the process, is the heart of mathematics as a human activity.
- sillysaurus3 9y agoThis isn't really true. Many proofs often start as dozens or hundreds of pages long, yet the creator is credited with advancing mathematics. It isn't till later that someone else comes along and simplifies the proof.
- kmill 9y agoBut the thing which constructs the proof might be what we will consider to be an "elegant proof." It might be more unsatisfying not being able to understand exactly why something is true, but computers can greatly expand the reach of what we can know.
- jessaustin 9y agoHaha this is the first thing I've heard about mathematics that reminds me of statements I've heard about chess. It's interesting to imagine a future in which useful math supporting useful tech is done by brutish AIs, while elegant math is the last refuge of humanity.
- tempay 9y agoCan't these proofs be useful in the context of "given that X is true we can say that"? In that case it doesn't matter how X was proven, it just provides a tool for future mathematics.
- bmc7505 9y agoHas there ever been a brute force proof that discovered the existence of a solution previously thought impossible? Something like a new tiling or proof by contradiction that found a positive example?
- qubex 9y agoIf I do not remember incorrectly, the proof of the Four Colour Theorem is essentially a brute-force one: a method of generating every possible graph that represents adjacency of tiling polygons on a 2D surface, and a subsequent colouring scheme for each and every one of them that never uses more than the desired four colours.
- kmill 9y agoThere is a step in the proof which is brute force. The proof is sort of giving a recursive algorithm for 4-coloring: for certain subgraphs, you simplify it, color the result, and use the coloring to color the original graph. There are 633 cases ("reducible configurations") in the recursion, and the annoying part is checking that all 633 actually work. After Haken and Appel, Gonthier wrote a Coq proof http://www.ams.org/notices/200811/tx081101382p.pdf http://www.ams.org/notices/200811/tx081101382p.pdf Sometimes I imagine that if we had much larger short term memories, an argument with only 633 cases would be obvious.
- opportune 9y agoI think the FCT proof doesn't generate every possible graph in that category (as there are infinitely many of them) but rather enumerates a very large set of compositional planar graphs such that all planar graphs are composed of combinations of subgraphs within the enumerated set
- qubex 9y agoYes, I think you are correct. I looked at it, and I looked into it, but only to grasp the general gist of it. The point was that essentially they reduced the infinite opportunities for tiling to a finite set of graphs whose composition covered the full spectrum of cases.
- janci 9y agoI hesitated before clicking on that link as for a second I thought it would start downloading that 200 TB proof.
- munificent 9y agoI really wish I'd known there would be an illustration of a naked woman in an advertisement on the right before I opened this at work.
- sharemywin 9y agosorry didn't see that. ad blind-ness.
- sheepdestroyer 9y agoDid not see it, shouldn't you use an adblocker at work for obvious reasons?
- Koshkin 9y agoSure, "proof mining" is feasible, but the goal of proving a theorem is only rarely finding any proof, it is rather finding a proof that makes sense, is "elegant", and in the best case scenario a proof that actually forms a sensible new theoretical framework in which the theorem becomes almost trivial to prove.
- raverbashing 9y agoNot really A proof that works is the most important part. After that you can make it nice
- Koshkin 9y ago> you can make it nice Not the 200 terabyte one, you can't.
- fosap 9y agoMaybe we can use the brute force of a "math superoptimizer" to "compress" it to something far more reasonable. If we teach said opimizer what structures are well understood by humans we might actually understand at last parts.
- nbates80 9y agoI don't know why people keep thinking there's something special about the way we humans do calculations vs what could be achieved with a complex enough computer
- AstralStorm 9y agoThese are not mere calculations. See, an understandable proof has more structure than plain first order logic alone. This allows such proofs to be extended and worked upon as well as real life implications to be discovered.
- fosap 9y ago
- pervycreeper 9y agoAssuming progress continues long enough: as proofs (and theorems) become more complex, the computational difficulty of verification, combined with the inherent physical impossibility of obtaining absolute certainty in the correctness of a computation will transform future mathematics into an empirical science, where mathematical hypotheses will be tested by computer, and results will be considered true only probabilistically.
- colordrops 9y agoThat wouldn't be a proof though. The article is about exhausting the problem space rather than a probabilistic approach.
- pervycreeper 9y ago>That wouldn't be a proof though. The article is about exhausting the problem space rather than a probabilistic approach. Not what I'm saying. I would suggest that absolute certainty is impossible wrt verifying conventionally proved theorems as well.
- colordrops 9y agoI think you moved the goal posts and are now talking about philosophy, not math. If you are saying all math is probabilistic even with conventional theorems, how can you predict a future of probabilistic math if it's already here?
- pervycreeper 9y ago> are now talking about philosophy, not math Call it what you will. > If you are saying all math is probabilistic even with conventional theorems, how can you predict a future of probabilistic math if it's already here? One crucial difference is that our confidence level in a given proposition will be made explicit and will be quantified. I think you are misinterpreting what I'm saying as well-- the "experiments" I'm suggesting are not naive monte carlo simulations or tests of a nonexhaustive sample of special cases, but the generation of formal logical proofs (although not necessarily limited to that). The uncertainty would arise physically from the largeness of the computation, and once that barrier is crossed, it's conceivable that other (less rigorous) methods could be added to the battery of techniques as well (thereby increasing confidence). Also note that the size (amount of information) of the theorems and proofs would be large, and perhaps will surpass human comprehension, even after multiple stages of approximation and abstraction. The degree of confidence in such theorems would also be close to certainty as well. No human readable proofs would be harmed in the process, except for the false ones!
- hellbanner 9y agoWhat did it prove?
- curiousgal 9y agoTheorem — The set {1, . . . , 7824} can be partitioned into two parts, such that no part contains a Pythagorean triple, while this is impossible for {1, . . . , 7825}.
- hellbanner 9y agoWow, interesting. Is the 200 terabyte proof necessary for that -- could it be refactored into something smaller?
- pcmaffey 9y agoI can't wait for the day when a proof is 'discovered' that no one can comprehend.
- krallja 9y agoA 200TB proof is already incomprehensible to humans. The average reading speed is 200wpm. The average human lifespan is 79 years, or about 41.5 million minutes. If you did nothing but read at 200wpm for your entire life, you might read 8.30 billion words. A word is 5.1 letters, on average, and in ASCII, a letter is one byte. Multiply that all together to get an estimated human reading speed of 42.4 GB/lifetime. It would take 4728 entire human lifetimes to read this proof once. This is vastly underestimating the actual number, due to silly things like "eating", "sleeping", "learning to read", etc.
- coldtea 9y ago>A 200TB proof is already incomprehensible to humans. Not really, since what matters is the compressibility of the proof, not its size. We might not be able to read all individual clauses, but it's enough that we know how the clauses are constructed.
- grondilu 9y ago> You could take a basic algebra problem as an example: 2x + 100 = 500. To solve this with brute force, we simply check every possible value of x until one works. We know, however, that it is far more efficient to rearrange the given equation using algebraic rules and in just two computations we get an answer. I gave some thoughts about this lately, and it occurred to me that it's a problem that is similar to how computers play chess. I'd like to know if I'm right. The equation 2x + 100 = 500 is an algebraic identity and with algebraic rules there is a finite number of ways to transform it. For instance, x + x + 100 = 500, 3x - x = 400, x + 200 = 600 - x, and so on. Each of these new equations can once again be transformed in a finite number of ways. So basically the initial equation is the root node of a tree that represents all the ways the equation can be transformed. So it's a similar problem than for chess, or many other board games, where you start from a position and you must explore a tree of possibilities to find the leaves (checkmates, for instance). For an equation the leaves are nodes of the form x = numeric value. Does that mean success in solving board games can have applications in computational math?
- nawgszy 9y agoSorry, this is just a trivial observation, but if you're going to accept x + x + 100 = 500 and 3x - x = 400 you can probably list any variety along the lines of (n)x - (n - 2)x + y = 400 + y so clearly that isn't a finite transformation space. Now, these transformations might look trivial, but this problem is too. So there's an interesting question of bounding your algebraic transformations to a subset of all possible transformations that still make all possible solutions available, which ultimately doesn't answer yours.
- grondilu 9y agoTrue, it is not finite. Still, considering the algorithm will not attempt to search the tree exhaustively anyway, maybe the fact that the tree is infinite does not make much difference. PS. On second thought the number of rules is finite, so the number of possibilities has to be finite, at least if you apply the rules one at a time. It's the iteration of the rules that makes the tree infinite.
- GnarfGnarf 9y agoThere's an error in the article. ((true AND false) OR true) AND NOT (true OR false) is false, not true as asserted in the article.
- cakebrewery 9y agoMaybe he corrected it afterwards but he clearly says it's not.
- phasnox 9y agoThis one is "from The Book" - P.E.
- deleted 9y ago[deleted]
- AstralStorm 9y agoA proof being valid does not mean the theory is useful or valid. If SAT was used, it means it is internally consistent in first order logic assuming the solver did not have a bug in it. (I bet the program was also verified.) You can simplify these proofs by extracting subproofs and replacing them from database by substitution. It is like compression but makes more sense.
- Radim 9y agoMandatory insight-vs-bruteforce-in-science essay: Peter Norvig, 2011: On Chomsky and the Two Cultures of Statistical Learning http://norvig.com/chomsky.html http://norvig.com/chomsky.html
- lotsoflumens 9y agoIt's disappointing that the authors use the term "brute force" to describe modern SAT solving, in an article intended for people who may not be familiar with the algorithms used. That term implies that the speed of the computer that was used to find the solution is the determining factor. It is not. Modern SAT solvers use very elegant search algorithms that have enabled the solution of SAT-encoded problems that could never have been solved if only "brute force" was used.