The original problem said "binary matrix" so surely that means mod 2? And I would expect mod 2 matrices to come up in the graph theory applications. Not that I know about that...
John On 22/02/2008, William Stein <[EMAIL PROTECTED]> wrote: > > On Fri, Feb 22, 2008 at 12:50 PM, David Harvey > <[EMAIL PROTECTED]> wrote: > > > > > > On Feb 22, 2008, at 3:49 PM, William Stein wrote: > > > > > > > > On Fri, Feb 22, 2008 at 12:04 PM, Jason Grout > > > <[EMAIL PROTECTED]> wrote: > > >> > > >> [EMAIL PROTECTED] wrote: > > >>> I've found a nice implementation of the DLX algorithm, which > > >>> "quickly" solves the NP-Complete exact cover problem. For those > > >>> who aren't in Seattle and haven't heard me blathering on and on > > >>> and on and on about how awesome DLX is... > > >>> > > >>> Let M be a binary matrix. An exact cover is a subset of the rows > > >>> of the matrix who sum (exactly) to the vector 1,1,...,1. > > >>> > > > > > > Isn't that exactly the same thing as solving > > > > > > M*x = [1,...,1], > > > > > > over GF(2)? > > > > I think it's probably not mod 2. > > > > david > > > Oh, that's a good point. I guess things become a lot easier when 1+1 = 0. > > > William > > > > > -- John Cremona --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
