Algebraic Models Of Computation: Understanding Vp And Vnp And Connections To Uniform Models Like Nc2 And #P

Understanding Polynomial Time Verification and Counting Problems

A central question in theoretical computer science is determining the computational complexity of important problems. While classes like P and NP characterize the difficulty of decision and search problems, algebraic models aim to capture the complexity of functions with numeric outputs. Two key complexity classes in this area are VP and VNP.

VP stands for “polynomial time verifiable functions” and contains function problems where the output can be efficiently verified given a certificate. VNP stands for “polynomial time verifiable number problems” and contains counting and enumeration problems associated with NP search problems. There are deep connections between VP, VNP, and uniform circuit complexity classes like NC2 and #P.

Defining the Complexity Classes VP and VNP

The complexity class VP contains multivariate polynomial functions over integers or rationals solvable in polynomial time by a random access machine. A VP machine gets input x, performs computations, and produces a numeric output f(x). Critically, there must exist a polynomial-size “certificate” c(x) that can be used to verify the output is correct.

Table of Contents

For example, matrix multiplication is in VP. Given input matrices A and B, a machine can multiply them to output C=AB. The full calculation serves as the certificate to verify C is the product. As matrix multiplication is computable in polynomial time, it is in VP.

The class VNP generalizes VP to also allow for counting and enumeration problems. A VNP machine associates polynomial-time verifiable numeric functions to languages in NP. Essentially, VNP contains all counting/enumeration versions of NP search problems. For instance, counting the satisfying assignments of a boolean formula or finding the number of Hamiltonian cycles in a graph.

Relation of VP and VNP to P and NP

There are several key set relationships between VP, VNP and traditional complexity classes P and NP:

P ⊆ VP ⊆ VNP: Efficiently computable functions are verifiable, VP allows polynomials, and VNP additionally enables counting for NP problems
VP = VNP if and only if P = NP: Counting/enumeration precisely captures the added difficulty of NP
VP ≠ VNP relative to an oracle: There exist oracles separating the two classes

A function is in VP if there is a polynomial-size certificate that makes verification easy. As P problems have efficient computations themselves, P ⊆ VP. VNP corresponds to counting for NP problems, capturing mathematically their increased complexity over P. If P = NP, counting solutions does not add difficulty, collapsing VP and VNP. Yet we strongly believe VP ≠ VNP, implying P ≠ NP.

Connections to Uniform Circuit Complexity Classes like NC2

VP and VNP are also connected to uniform circuit complexity classes like NC2 that capture problems efficiently solvable in parallel. Logspace-uniform NC2 circuits with polynomial size and O(log2 n) depth can compute polynomial functions with sufficient parallelism. In particular:

FP ⊆ NC2 ⊆ VP: Efficient parallel circuits can compute polynomials
PERM ⊆ NC2: Computing the permanent is hard but verifying is easy

While Newton’s identities allow NC2 computation of polynomial symmetries like the elementary symmetric polynomials, the permanent seems harder as permutations lack structure. So the permanent is in VP but suspected not to be in NC2. Separating VP and NC2 is an important open problem.

#P Functions for Counting and Enumeration

The complexity class #P contains the counting versions of NP search problems. A #P function FC takes an input x and outputs the number of witnesses y that satisfy a polynomial-time verifiable relation R(x,y). For instance, counting satisfying assignments of a Boolean formula in NP. #P is contained in the larger class FP that allows polynomial-time computable functions.

#P has an intimate connection with the class VNP. All #P functions have associated NP relations, so they are in VNP. The question if all of VNP is contained in #P remains open. Currently, we know:

#P ⊆ VNP
VNP could be a strictly larger class than #P

So VNP aims to characterize the algebraic difficulty of counting and enumeration problems for NP, while #P directly defines the countable functions.

Complete Problems for VNP

Two important VNP-complete problems that capture the essence of its counting/enumeration capabilities are:

#SAT: Counting the satisfying assignments of a Boolean formula in CNF form
Permanent: Computing the permanent of a 0-1 matrix, which lacks the structure of the determinant

If either of these problems could be solved in polynomial time, all problems in VNP could be as well, implying P=NP.

The permanent seems particularly fundamental as its #P-completeness persists even over finite fields, implying VNP=VP over all fields would collapse polynomial counting down to polynomial time solvability. The permanent thus embodies the algebraic difficulty of counting.

Algebraic Random Access Machines

A useful model for designing algebraic algorithms is the algebraic random access machine (ARAM). ARAMs extend traditional RAM models by including registers that can store rational numbers and a finite set of algebraic operations like addition, multiplication, comparison, and branching.

ARAMs natively allow the expression and analysis of algebraic algorithms, as opposed to encoding numerics indirectly via Turing machines with alphabet symbols. They provide a cleaner machine model for complexity classes defined over numeric functions like VP and VNP. Modern programming languages that support arbitrary precision numerics can be seen as physical ARAM implementations.

Arithmetic Circuits and Formula Size

Alternate models like arithmetic circuits and straight-line programs are also useful for studying VP and VNP. An arithmetic circuit consists of input nodes for variables and constants, arithmetic gates like addition and multiplication, and output nodes. The size or depth of a minimal circuit computing a function captures its complexity.

In a straight-line program, each step is given by an algebraic operation over previous values. The number of steps for a minimal straight-line program thus provides a formula size measure. Relationships between formula size and arithmetic circuit size help characterize VP versus VNP.

While permanent and determinant have exponentially sized formulas, the determinant has small uniform circuits. Separating power from uniformity remains crucial open area to understand the source of counting complexity.Future Research Directions

Understanding the boundary between easy and hard counting problems remains central in complexity theory today. Some promising research directions include:

Separating VP from VNP by finding an explicit function family in VNP but not VP
Studying restricted models like constant-depth arithmetic circuits
Using algorithms and hardness approximation for matrix permanent to explore VP vs VNP border
Leveraging algebraic geometry tools like degeneration and part connections

There remain only a few promising approaches to possibly resolve the power and limitations of efficient verification versus counting. The algebraic framework of VP versus VNP provides the right level of abstraction to structurally characterize the intrinsic complexity of counting.