5 ms·
An AI has solved several open problems in combinatorics and graph theory
- YeGoblynQueenne 5y ago>> To get a sense for how reinforcement learning can be used to uncover counterexamples, consider this scenario. Suppose there is a mathematical conjecture predicting that the expression 2x – x2 is negative for any real value of x. This conjecture isn’t true — and you can prove that by producing a value of x (a counterexample) for which it’s false. (Any number between 0 and 2 is a counterexample, with the value of 2x – x2 peaking at x = 1.) That sounds like a constraint solving problem. Did the author compare his system to a constraint solver, or try to derive the same proofs by constraint solving?
- porcoda 5y agoThe author does mention problems where LP solvers can be used to solve the problems instead of the neural network approach used for the others. See section 3 in https://arxiv.org/pdf/2104.14516.pdf https://arxiv.org/pdf/2104.14516.pdf.
- rowanG077 5y agoLinear problems are very, very limiting though.
- jnash 5y agoAgree. This is bread and butter for SMT solvers like Z3. No "AI" required.