Wednesday, October 25, 2017

Day 25

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

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

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 a1s(1)...ans(n).