Boolean Circuit Lower Bounds & Permanent Complexity Lab (VP vs VNP)

Circuit Family:

Matrix Size (n): 3 x 3

Circuit Model:

Max Fan-In:

Matrix Inputs X

Assign values to variables $x_{ij}$ to observe live gate evaluation across the DAG.

Step-by-Step Evaluation

Current Value Computed:

Perm = 0

Ready to evaluate circuit outputs.

Lower Bound Formula

Size: O(2^(n-1) * n) | Depth: O(n)

Ryser's inclusion-exclusion formula achieves $O(2^n n)$ operations, optimal for general arithmetic circuits.

Matrix Input ($x_{ij}$)

Addition / OR Gate

Multiplication / AND Gate

Circuit Output

Circuit Complexity Scaling

Circuit Topology Metrics

Total Gates (Size):19

Circuit Depth:3

Max Algebraic Degree:3

Complexity Class:VNP-complete

Polynomial Approx Error:2^-d

Lean 4 Lower Bound Certificate

-- Verification of Circuit Lower Bound
theorem permanent_vnp_hard (n : ℕ) :
  CircuitSize (Permanent n) ≥ 2^(n-1) * n :=
begin
  -- Ryser Inclusion-Exclusion lower bound
  sorry
end
        

DAG Rendered: 19 gates generated for 3x3 Permanent circuit via Ryser's formula. VP ≠ VNP Computational Laboratory