sdo@linus.UUCP (Sean D. O'Neil) (02/16/89)
In article <9775@nsc.nsc.com> andrew@nsc.nsc.com (andrew) writes: >A recently addressed "solution" by supercomputer to a long-standing maths >conjecture - that of the finite projective plane - now exists for planes up >to order 10 (Science News, Dec 24 & 31, 1988), whereby 1000's of hours >of Cray time was needed! This looks like a nice place for a net and a Cray >to do battle... the constraints are simply expressed: >- for order k, construct a square matrix with k**2 + k + 1 rows/columns >- fill the matrix with 0's and 1's, such that: > - every row contains exactly k + 1 1's > - every possible pair of rows has exactly one column in which > both have a '1' Hmmm. Sounds to me like there is some confusion going on here. Let's recall that what was proved was that there is NO finite projective plane of order 10. This was done by showing that no 0-1 matrix of the given type existed for order 10. The contribution of the people involved was to somehow restrict the search of candidate 0-1 matrices so that it only took thousands of hours on a Cray (as opposed to the lifetime of the universe). Now Andrew is proposing to do the 0-1 matrix search on a neural net. However, for order 10 he's not going to find one that satisfies the constraints. What will the neural network output be that will allow us to say, as the Cray people were able to say, that there is NO finite projective plane of order 10? Is his network such that we can *definitively* state it will always find a solution if one exists (thereby allowing us to interpret a negative result as a non-existence proof)? I suspect not. Therefore, it's hard for me to see what, if any, comparison can be made with the Cray 'proof' in this case. >I have successfully solved this for low orders using the linear "schema" ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >cs (constraint satisfaction) program from "Explorations...PDP". Exactly. Finite projective planes exist for all orders less than 10 and greater than 1, except for 6 (they are known to exist for orders equal to a prime or a power of a prime). What did the neural net do for order 6? Perhaps Andrew means to search for finite projective planes of order greater than 10 for which we do not know how to do an explicit construction. I believe order 12 is the next case where the results are unknown (in addition to orders for which we know how to explicitly construct finite projective planes, there is a theorem proving that there are no finite projective planes for some other infinite set of orders---I believe 14 is in this set). If one could find a finite projective plane of order 12, that would be an impressive result. I wish him luck, but I am skeptical. Remember, the constraints are hard in the sense that they must be exactly satisfied. Approximate solutions don't count. Sean
andrew@nsc.nsc.com (andrew) (02/18/89)
Hmmmm. Re-phrase your title: "prove non-existence with neural net?" to
"prove existence after termination with neural net" and all becomes clear.
Perhaps Sean is being unduly pessimistic. Perhaps Sean realises that if
an FPP can be found - e.g. by a neural net - that is of an order
formally excluded by conjecture - then that conjecture is disproved.
The nice thing thing about the net idea is how it scales with order.
Order **6 is much nicer than (NcK)**N, but of course this is, as he
point out, apples with non-exhaustive pears. "Exactly" is quite easy -
just look at the NN settled state, and count 1's for a few seconds.
This is eyeball and brain territory, and no big deal. For lack of
decent simulation x-ware, I'm unable to say what happens with order 6.
Andrew Palfreyman, MS D3969 PHONE: 408-721-4788 work
National Semiconductor 408-247-0145 home
2900 Semiconductor Dr. there's many a slip
P.O. Box 58090 'twixt cup and lip
Santa Clara, CA 95052-8090
DOMAIN: andrew@logic.sc.nsc.com
ARPA: nsc!logic!andrew@sun.com
USENET: ...{amdahl,decwrl,hplabs,pyramid,sun}!nsc!logic!andrewsdo@linus.UUCP (Sean D. O'Neil) (02/23/89)
In article <9905@nsc.nsc.com> andrew@nsc.nsc.com (andrew) writes: >Hmmmm. Re-phrase your title: "prove non-existence with neural net?" to >"prove existence after termination with neural net" and all becomes clear. > >Perhaps Sean is being unduly pessimistic. Perhaps Sean realises that if ^^^^ ^^^^ , Touche. I apologize if my previous note sounded patronizing---that was not my intention. >an FPP can be found - e.g. by a neural net - that is of an order >formally excluded by conjecture - then that conjecture is disproved. I agree totally that the contribution the neural network can make is to find an FPP. Where my original concern arose was with the idea of comparing the neural network with the Cray (i.e. "do battle") on this order 10 example since the contribution of the Cray was to help prove the non-existence of an FPP of order 10. I think we both agree that the neural network setup you are talking about cannot help us prove non-existence (correct me if I am wrong on assuming this, as it's an important point). Therefore, we cannot interpret the results of the Cray and the results of the neural network in the same manner (i.e. a positive result for either proves existence, while a negative result for the Cray proves non-existence, but for the neural network proves nothing). Thus, it would be impossible to state whether the neural network or the Cray is `better' at this particular task, as the tasks they are carrying out are not identical (i.e. the Cray is performing a task that comes out with a stronger result). >The nice thing thing about the net idea is how it scales with order. >Order **6 is much nicer than (NcK)**N, but of course this is, as he >point out, apples with non-exhaustive pears. "Exactly" is quite easy - >just look at the NN settled state, and count 1's for a few seconds. >This is eyeball and brain territory, and no big deal. For lack of I agree that checking whether the answer matches the constraints is trivial. >decent simulation x-ware, I'm unable to say what happens with order 6. I think the contribution that could be made here is to find an FPP of order 12, if such a thing exists (read my previous note for details). Depending on the amount of effort required to set up the proposed neural network search, I might want to have some reasonable assurances that it would find an FPP if it existed. What such assurances should be are, of course, a matter of opinion. Sean