SAT and P vs NP

CREATED: 200912221647 Geometric complexity theory: #P (related to compute permanent of matrix), NP, P, NC (related to computing determinant of matrix)

Use #P vs NC as a proxy for P vs NP Able to prove weak form of #P vs NC

Barriers to P vs NP:

• relativization
• natural proofs

CH and AC are independent of ZF

Forcing is only known method to show independence.