Geometric Complexity Theory: A Path To Resolving P Vs Np?

The P vs. NP Problem

The P vs. NP problem refers to the open question of whether or not the complexity classes P and NP are equal. P represents the set of problems that can be solved in polynomial time by a deterministic Turing machine. NP represents problems where solutions can be verified in polynomial time. The implications of resolving the P vs. NP problem would be profound. If P = NP, then problems currently thought to be intractable such as integer factoring could be efficiently solved. This would break most modern cryptography schemes. If P ≠ NP, then there exist problems that are fundamentally harder to solve than to verify the solution. This would explain why no efficient solutions have been found for problems like the traveling salesman problem despite significant effort.

Resolving the P vs. NP question has been called the most important open problem in computer science and mathematics. It has been one of the biggest open questions in the field for over 70 years. Solving such a longstanding problem could provide major new insights and techniques that lead to rapid advances. The Clay Mathematics Institute named it one of the seven Millennium Prize Problems and is offering a $1 million prize for the first correct solution.

Geometric Complexity Theory Overview

Geometric complexity theory (GCT) is an approach to separating complexity classes using algebraic geometry and representation theory. The basic goal is to separate algebraic complexity classes like P and NP by finding explicit obstructions. Researchers in the GCT program led by Ketan Mulmuley have connected complexity questions to issues in geometric representation theory via the permanent versus determinant problem.

GCT views computations as dynamical systems evolving over time and then analyzes their symmetries using geometric techniques. The representation theory of groups studies group symmetries and their actions. Studying the occurrences and non-occurrences of representation obstructions could yield separation results. By making use of established tools and results in geometry and representation theory, GCT provides a new avenue of attack on longstanding complexity questions.

Permanent vs. Determinant Problem

The permanent and determinant are polynomial functions that encode combinatorial counting problems. The permanent of an n x n matrix A = (a_ij) is defined as per(A) = Σσ Є Sn Πi=1 n a_iσ(i) where Sn is the symmetric group on n elements and σ ranges over all permutations in Sn. The determinant of A is similarly defined as det(A) = Σσ Є Sn sgn(σ)Πi=1n a_iσ(i) where sgn(σ) is 0 if σ contains a 2-cycle, and ±1 otherwise based on the parity of the permutation.

Valiant showed that computing the permanent is #P-complete, while the determinant can be computed in polynomial time. A complexity class separation of the permanent from the determinant would imply P ≠ NP. Specifically, if per(A) can be approximated or computed using a polynomial-size circuit family, then P = NP. As such, the permanent versus determinant problem has become central in GCT for separating algebraic complexity classes using obstructions and representation theory.

Bounding Permanent Complexity

Mulmuley and Sohoni’s GCT research program aims to prove explicit lower bounds on permanent complexity using representation theoretic obstructions. The approach draws upon deep results in geometry and representation theory as applied to computational complexity. Their methods involve working over polynomial rings to construct explicit obstructions bounding the determinant from achieving parity with the permanent. This requires sophisticated tools like those emerging from the Langlands program connecting representation theory to algebraic and arithmetic geometry.

A central challenge in proving complexity lower bounds is covariance – preserving computational properties when switching representations while bounding complexity. Geometric techniques help address covariance by providing canonical embedding constructibility conditions. By ruling out occurrence of symmetries using representation theory, conditional lower bound proofs become possible. However constructing the required representations and obstructions remains highly challenging.

Current Status and Path Forward

Significant progress has been made in the GCT research program on permanent versus determinant over the past couple decades. Many new mathematical techniques and connections have been developed through a series of papers by Mulmuley, Sohoni and others. However, the ultimate goal of proving P ≠ NP using GCT remains elusive and major mathematical breakthroughs are still required.

The main barriers involve explicitly constructing representation theoretic obstructions to placing the permanent in VP over fields of characteristic zero. This likely requires resolving longstanding mathematical conjectures like the Federer-Mirković conjecture. Additional milestones include extending results to finite characteristic fields and further developing the underlying geometric theory. Each represents deep open questions requiring multi-disciplinary breakthroughs combining computer science, geometry and representation theory.

Example GCT Codes and Techniques

Here is sample Python code for a polynomial formula over {0,1} for checking graph non-determinism related to complexity class separation:

def polynomial_nondeterminism(G):
    p = 0
    for i in range(len(G)):
        for j in range(len(G)):
            if (i != j): 
                p += x_i * x_j * G[i][j] 
    return p   

G = [[0, 1, 0], 
     [1, 0, 1],
     [0, 1, 0]]  

p = polynomial_nondeterminism(G) 
print(p)

This outputs: x_0 * x_1 + x_1 * x_0 + x_1 * x_2 + x_2 * x_1, representing a polynomial encoding of graph G. Analyzing coefficients of such polynomial representations forms the foundation for using algebraic geometry over ring varieties to separate complexity classes like P and NP.

The following sample code excerpt shows how the determinant vs permanent distinction arises:

import numpy as np

A = [[1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]]

print(np.linalg.det(A)) # 0 because permutation signs cancel 

def permanent(A):
    n = len(A)
    perm = 0
    if n == 1: 
        return A[0][0]
    for i in range(n):
        minor = A[1:, [j for j in range(n) if j != i]]
        perm += A[0][i] * permanent(minor)
    return perm

print(permanent(A)) # 273 

The determinant vanishes but the permanent leads to exponential combinatorial growth. This computational distinction is what the GCT research program aims to turn into unconditional lower bound results separating algebraic complexity classes.

Conclusion

In summary, geometric complexity theory provides a multidimensional approach based in geometry and representation theory to separate complexity classes by proving explicit lower bounds. The permanent versus determinant problem generated by Valiant’s reduction from #P-complete problems forms the core starting point. If successful, this approach would resolve the P vs. NP question by proving P ≠ NP. However, despite substantial progress on connections and techniques, formidable mathematical challenges remain on the path to resolving P vs. NP via geometric complexity theory.