3 ms·
Why would this be hard for the machines? A lot of math contest problems are about trying some rearrangements or substitutions, using a few principles to guide y
by lordnacho 7y ago
Why would this be hard for the machines? A lot of math contest problems are about trying some rearrangements or substitutions, using a few principles to guide you towards the solution.
If you give the machine some equations, wouldn't it find a path to the solution pretty fast? Aren't there solvers that aren't considered AI that do that sort of thing?
I did some math contests in school, and a lot of the problems needed some brute force element along with a bit of overview so you didn't waste too much time. Often there'd be a problem that you'd look at and think "hmm this will solve via integration by parts" but the thing was complex enough that you'd potentially screw something up.
I looked in the Gitlab, it seems the problems are already encoded in Lean. Haven't you solved a major part of the problem already if you can formally encode it like that? Half the fun of math contests is getting over the WTF feeling.
- throwaway-ai-ai 7y agoSuppose your assertion about this problem being easy was true. Most research papers in Math / Theoretical CS are < 50 pages, while many IMO problems have solutions > 1 page. So it's only a factor of 50 "more complex." Then, we should be able to encode open problems / conjectures in Math / Theoretical CS into Lean, run this brute fore approach, and have it start auto generating new publications. To the best of my knowledge, no one has done this yet.
- eru 7y agoWell, the IMO problems are constructed with a solution in mind. Also, who says that efforts goes up linearly with size? (Not necessarily agreeing with lordnacho here, just saying that your argument ain't a good one.)
- NieDzejkob 7y agoThat's a good point. If we assume each line of a publication is just applying an axiom, the complexity of such a search is clearly exponential in the length of an article. I feel like this wouldn't be better if we dropped the assumption.
- oefrha 7y agoComplexity is a terrible measure of mathematical value. Length of exposition is even worse.
- saagarjha 7y ago> hmm this will solve via integration by parts The AMC/AIME/USAMO/IMO set of exams can all be solved without calculus and are not what I'd call "brute force". Perhaps you have experience with a different type of mathematical competition?
- lordnacho 7y agoPerhaps brute force is the wrong term, but at least they would require a chain of transformations that a human could easily mess up. Rearranging, substituting, etc. A machine wouldn't get that wrong ever, whereas a human would have wasted a fair bit of time. Well I did miss the IMO team narrowly, but I didn't think those questions were all that different in nature. Quirky questions you'd never see in school, but solvable with school tools. And I'm pretty sure that while you didn't NEED calc and higher subjects, having studied them would give you some edge.
- saagarjha 7y agoMaking algebraic mistakes is always a possibility with human test-takers, but the questions are usually designed that the work isn't too bad. They could absolutely do a lot worse if they didn't try to make the math work out nicely. I'm more concerned about trying to teach computers which chain of transformations they should be looking into and how to perform them.
- elil17 7y agoYou should take a look at the IMO problems - they are generally very different from any sort of math problem you’ve ever seen before. For instance: Determine all finite sets S of at least three points in the plane which satisfy the following condition: for any two distinct points A and B in S, the perpendicular bisector of the line segment AB is an axis of symmetry for S. This is a deeply abstract and complex problem.
- MauranKilom 7y agoThat was an IMO problem? How long ago was this? I'm just surprised because I found the solution set + proof in like 5 minutes of writing elementary observations on a sheet of paper... (Very much unlike the IMO qualifying test I took a few years ago. Couldn't even produce a meaningful sketch of the geometry in question there...) --- quick solution sketch --- - every regular polygon is an obvious solution - no three points can be collinear (can't have distinct parallel symmetry axes) - for a given solution, look at all (3+) symmetry axes - they have to meet at the same point (easy to prove by contradiction) - thus the angles between "neighboring" axes must be constant, namely PI / n for a solution with n distinct axes - since any solution has to fulfill the above, for a given n > 2 we can draw all the axes (intersection point and "phase" are degrees of freedom). Add one point and mirror it on all axes - if no new axes are added (and you now have > 2 points, i.e. didn't put the initial point at the center) it's a valid solution. (You can't add another point afterwards - it would form a new axis with the first one). - some footwork left to conclude that only "starting points" that produce regular polygons fulfill that. A proof by contradiction is pretty obvious in a sketch, but takes some effort to get even/odd n-gons covered correctly - there's probably something more elegant, but at this point you already know you've got the proof down. While writing this out I realized that all the points must lie on a circle (apply circle chord perpendicular bisector theorem to "successive" point pairs) which should help simplify the proof. (Please point out any mistake/misunderstanding - the solution seems way too trivial for an IMO problem. Well, a recent one at least.)