Complexity theory is a mathematical study of algorithmic problems with regard to how cost-effective solutions they have. Most prominent are the decision problems, which are yes-no questions for which answer depends on some further input, for example, “Is \( n\) a prime number?” is a decision problem depending on the input \( n\). I assume that a reader of this post has some familiarity with the basic concepts of this theory, in particular, what PSPACE complexity class is and what does it mean that a problem is PSPACE-complete. A well-known theorem due to Shamir states that the class PSPACE and another class, IP (which I explain below, since I wouldn’t count it as a “basic” concept), are equal. The goal of this post is to prove this theorem. It is not based on a single source, but there is a very detailed exposition due to B.J. Mares, which I shall leave as a reference.

Read More