Xref: utzoo sci.math:11844 comp.theory:905
Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!ucsd!ames!pasteur!mandolin.Berkeley.EDU!grove
From: grove@mandolin.Berkeley.EDU (Eddie Grove)
Newsgroups: sci.math,comp.theory
Subject: Re: Permanents and determinants
Message-ID: <26574@pasteur.Berkeley.EDU>
Date: 30 Jul 90 20:49:04 GMT
References: <37817@ucbvax.BERKELEY.EDU>
Sender: news@pasteur.Berkeley.EDU
Reply-To: grove@mandolin.Berkeley.EDU (Eddie Grove)
Organization: University of California at Berkeley
Lines: 18

In article <37817@ucbvax.BERKELEY.EDU> greg@brahms.berkeley.edu (Greg Kuperberg) writes:
>Suppose in general you have an n x n matrix M, and you can obtain
>a list of matrices M1,...,Mk by changing the signs of the entries
>of M with the property that the permanent of M is a linear combination
>of the determinants of M1,...,Mk.  How small can you make k?  For
>n=4, k=4 by the above example.  How about for n=5?
>-----
>Greg Kuperberg
 
This is going to be an extremely difficult problem for general k.
 
Calculating the permanent is #P-complete, while determinant is in P.
 
So if you can prove k to be polynomial in n, or lower bound it
by a super-polynomial, you get a tremendous result in complexity
theory.
 
Eddie Grove