Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!amdahl!pyramid!prls!philabs!linus!sdo
From: sdo@linus.UUCP (Sean D. O'Neil)
Newsgroups: comp.ai.neural-nets
Subject: Prove non-existence with neural net?
Summary: Run this one by me again
Keywords: Cray, finite projective plane, confusion
Message-ID: <44911@linus.UUCP>
Date: 15 Feb 89 18:29:15 GMT
References: <1637@cps3xx.UUCP> <1233@usfvax2.EDU> <476@madnix.UUCP> <9775@nsc.nsc.com>
Reply-To: sdo@faron.UUCP (Sean D. O'Neil)
Organization: The MITRE Corporation, Bedford MA
Lines: 58

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