Day 25

Showed that AM in Π₂^P and MA in Σ₂^P∩Π₂^P and if AM is in co-NP then PH collapses to Σ₂^P.

This implies that if Graph Isomorphism is NP-complete then PH collapses to Σ₂^P.

Introduced counting complexity, #P and the Permanent.

A function f:{0,1}^*→ℕ is in #P if there is an NP machine M such that f(x) = the number of accepting paths of M(x).

The permanent of a matrix A is the sum over all permutations s of a_1s(1)...a_ns(n).