Complexity Theory --- The World of P and NP
主 题: Complexity Theory --- The World of P and NP
报告人: Prof. Jin-Yi Cai (Uinversity of Wisconsin, Madison)
时 间: 2009-10-30 下午14:00 - 15:00
地 点: 理科一号楼 1114(数学所活动)
The study of computational complexity presents challenging mathematicalproblems. In Complexity Theory computational problems are classifiedinto complexity classes, the best known include P, NP and Valiant'sclass #P for counting problems.A central problem in Valiant's theory is the permanent vs. determinantproblem. We will report some latest progress on this problem.Graph homomorphism was introduced by Lovasz over 40 years ago, and it isalso called the partition functions in Statistical Physics, and canencode a rich class of counting problems:Given an $m \times m$ symmetric matrix $A$ over the complex numbers,compute the function $Z_A(\cdot)$, where for an arbitrary input graph $G$,\[ Z_A(G) =\sum_{\xi:V(G)\rightarrow [m]} \prod_{(u,v)\in E(G)} A_{\xi(u),\xi(v)}.\]Our foucs is the computational complexity of $Z_A(\cdot)$.With Xi Chen and Pinyan Lu, we have achieved a complete classificationtheorem for the complexity of $Z_A(\cdot)$.The classification proof is too complicated to present, butwe will present the proof of a lemma.It states that in order to be computable in polynomial time,the matrix $A$ must possess a group structure. Another componentof the proof uses Gauss sums.No prior knowledge of complexity theory is assumed.
