Binary determinantal complexity
Copyright policy )Binary determinantal complexity
We prove that for writing the 3 by 3 permanent polynomial as a determinant of a matrix consisting only of zeros, ones, and variables as entries, a 7 by 7 matrix is required. Our proof is computer based and uses the enumeration of bipartite graphs. Furthermore, we analyze sequences of polynomials that are determinants of polynomially sized matrices consisting only of zeros, ones, and variables. We show that these are exactly the sequences in the complexity class of constant free polynomially sized (weakly) skew circuits.
10 pages, C source code for the computation available as ancillary files
- Technical University of Berlin Germany
- Technical University of Berlin Germany
- The University of Texas System United States
- Texas A&M University United States
FOS: Computer and information sciences, computational complexity, Analysis of algorithms and problem complexity, Determinants, permanents, traces, other special matrix functions, Computational Complexity (cs.CC), Enumeration in graph theory, determinant, permanent, Computer Science - Computational Complexity, 68Q05, 68-04, arithmetic circuit, Complexity classes (hierarchies, relations among complexity classes, etc.), constant-free, F.1.1
FOS: Computer and information sciences, computational complexity, Analysis of algorithms and problem complexity, Determinants, permanents, traces, other special matrix functions, Computational Complexity (cs.CC), Enumeration in graph theory, determinant, permanent, Computer Science - Computational Complexity, 68Q05, 68-04, arithmetic circuit, Complexity classes (hierarchies, relations among complexity classes, etc.), constant-free, F.1.1
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!