The
P versus
NP problem is arguably the most important open problem in all of theoretical computer science. In recent years, geometry has arisen as one of the most promising approaches for tackling this problem, both for obtaining positive results (polynomial-time solutions to seemingly intractable computational problems) and for proving negative results (impossibility results stating that such algorithms cannot exist). This work deals with both directions. \nIn the positive direction, the theory of holographic algorithms introduced by Valiant represents a novel approach to achieving polynomial-time algorithms for seemingly intractable counting problems via a reduction to counting planar perfect matchings and a linear change of basis. The connection to geometry is that a counting problem can be solved by a holographic algorithm provided a particular system of equations associated to that problem is solvable. Two fundamental parameters in holographic algorithms are the \\emph{domain size} and the \\emph{basis size}. Roughly, the domain size is the range of colors involved in the counting problem at hand (e.g. counting graph
k-colorings is a problem over domain size
k), while the basis size
ell captures the dimensionality of the representation of those colors. A major open problem has been: for a given
k, what is the smallest
ell for which any holographic algorithm for a problem over domain size
k ``collapses to'' (can be simulated by) a holographic algorithm with basis size
ell? Cai and Lu showed in 2008 that over domain size 2, basis size 1 suffices, opening the door to an extensive line of work on the structural theory of holographic algorithms over the Boolean domain. Cai and Fu later showed for signatures of full rank that over domain sizes 3 and 4, basis sizes 1 and 2, respectively, suffice, and they conjectured that over domain size
k there is a collapse to basis size
lfloorlog2krfloor. In the first half of this work, we resolve this conjecture in the affirmative for signatures of full rank for all
k. As a simple consequence, we are able to formulate Valiant's holographic framework over all domain sizes in terms of the geometry of spinor varieties and their orbits under basis change. \nIn the negative direction, Valiant's conjecture is an algebraic analogue of
P versus
NP which states that the permanent polynomial
permm cannot be computed as a linear projection of the determinant polynomial
detn for
n=poly(m). This can be formulated as an orbit containment problem; for the sake of bringing tools from algebraic geometry to bear on Valiant's conjecture, Mulmuley and Sohoni conjectured that Valiant's conjecture still holds when one passes to the Zariski closures of the relevant orbits. Essential to understanding what changes in this relaxation is understanding the geometry of the boundary of the orbit closure of
detn. In the second half of this work, we study this problem for
n=3 and use a combinatorial approach to give a complete classification of the irreducible components on the boundary in this case. We additionally present a new infinite family of boundary components for all even
n. Beyond these results and a general overview of Mulmuley-Sohoni's program, we also provide exposition on known lower bounds for the determinantal complexity of the permanent in Valiant's and Mulmuley-Sohoni's settings, an exponential lower bound due to Landsberg and Ressayre under a more restricted model of determinantal representations, Kumar's result on the non-normality of the orbit closure of
detn, Harris and Eisenbud's classification of maximal linear subspaces of the determinantal hypersurface in dimensions 3 and 4, and Huttenhain-Lairez's independent proof of our boundary component classification by way of resolution of singularities.
We provide evidence for the proposition that the computational complexity of individual problems, and of whole complexity classes, hinge on the existence of certain solvable polynomial systems that are unlikely to be encountered other than by systematic explorations for them. We consider a minimalist version of Cook's 3CNF problem, namely that of monotone planar 3 CNF formulae where each variable occurs twice. We show that counting the number of solutions of these modulo 2 is oplusP-complete (hence NP-hard) but counting them modulo 7 is polynomial time computable (sic). We also show a similar dichotomy for a vertex cover problem. To derive completeness results we use a new holographic technique for proving completeness results in oplusP for problems that are in P. For example, we can show in this way that oplus2CNF, the parity problem for 2CNF, is oplusP-complete. To derive efficient algorithms we use computer algebra systems to find appropriate holographic gates. In order to explore the limits of holographic techniques we define the notion of an elementary matchgrid algorithm to capture a natural but restricted use of them. We show that for the NP-complete general 3 CNF problem no such elementary matchgrid algorithm can exist. We observe, however, that it remains open for many natural #P-complete problems whether such elementary matchgrid algorithms exist, and for the general CNF problem whether non-elementary matchgrid algorithms exist
We introduce an idea called anti-gadgets for reductions in complexity theory. These anti-gadgets are presented as graph fragments, but their effect is equivalent to erasing the presence of other graph fragments, as if we had managed to include a negative copy of a certain graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function Z ( G ) of spin systems over 3-regular directed graphs G , Z ( G ) = ∑ σ : V ( G ) → { 0,1} ∏ ( u , v ) ∈ E ( G ) f (σ ( u ), σ ( v )), where each edge is given a (not necessarily symmetric) complex-valued binary function f : { 0,1} 2 → C. We show that Z ( G ) is either computable in polynomial time or #P-hard, depending explicitly on f . When the input graph G is planar, there is an additional class of polynomial time computable partition functions Z ( G ), while everything else remains #P-hard. Furthermore, this additional class is precisely those that can be transformed by a holographic reduction to matchgates, followed by the Fisher-Kasteleyn-Temperley algorithm via Pfaffians.
We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (\#CSP) over Boolean variables into exactly three classes: (1) polynomial-time solvable; (2) \#P-hard for general instances but solvable in polynomial time over planar structures; and (3) \#P-hard over planar structures. The classification applies to all finite sets of local, not necessarily symmetric, constraint functions on Boolean variables that take algebraic complex values. It is shown that Valiant's holographic algorithm with matchgates is a universal strategy for all problems in class (2).
We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#CSP) over Boolean variables into exactly three classes: (1) Polynomial-time solvable; (2) #P-hard for general instances, but solvable in polynomial-time over planar structures; and (3) #P-hard over planar structures. The classification applies to all finite sets of complex-valued, not necessarily symmetric, constraint functions on Boolean variables. It is shown that Valiant's holographic algorithm with matchgates is universal strategy for all problems in class (2).
Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.