Posts tagged Complexity Theory

I am taking the complexity course this semester, and the professor has given us assignments to write wikipedia articles about particular complexity topics. We have groups for writing each article, and so far we have completed two articles. It’s quite an interesting exercise. Check them out

• TQBF – True Quantified Boolean Forumla. It’s PSPACE-complete and the article explains the proof in easy-to-understand words.
• Permanent is #P-Complete. The proof is a little complex, but we tried our best to show the intuition behind all the steps.