Lecture Notes: Polynomial Hierarchy and Related Concepts

Author

Your Name

Published

January 28, 2025

Introduction

This lecture delves into the intricacies of the polynomial hierarchy (PH), exploring its various facets, including alternative definitions and connections to other complexity classes. We will investigate the crucial role of certificates in defining complexity classes within the PH. Furthermore, the concept of quantified Boolean formulas will be introduced, providing a powerful tool for understanding and characterizing these classes. The lecture will also cover the relationship between the polynomial hierarchy and other important complexity classes such as PSPACE, EXP, and NEXP.

In addition to the theoretical foundations, we will bridge the gap between abstract concepts and practical applications by examining trace equivalence and bisimulation in the context of automata. We will use an example involving a coffee machine and an insurance contract to illustrate the differences between these two concepts and how they relate to system verification. This will shed light on how these notions are employed in the crucial field of system verification and why choosing the correct notion of equivalence is critical. Finally, we will briefly discuss the concept of succinct circuit representation and its impact on the complexity of circuit problems.

Polynomial Hierarchy (PH) and its alternative definitions
Certificates and their role in defining complexity classes
Quantified Boolean Formulas
Complexity Classes: PSPACE, EXP, NEXP
Trace Equivalence and Bisimulation in Automata
Applications in System Verification
Succinct Circuit Representation

The lecture will use illustrative examples and connect theoretical concepts to practical applications in system verification. The concepts introduced in this lecture are fundamental for understanding the landscape of computational complexity and its implications in various domains.

Polynomial Hierarchy

Definition using Oracles

The polynomial hierarchy (PH) is a hierarchy of complexity classes that generalizes the classes NP and coNP. It is defined recursively using the concept of oracle machines.

Base Case:
- $\Sigma_0^P = \Pi_0^P = \Delta_0^P = P$
- $\Sigma_1^P = NP$
- $\Pi_1^P = coNP$
- $\Delta_1^P = P$
Inductive Step: For $i \geq 1$
- $\Sigma_{i+1}^P = NP^{\Sigma_i^P}$ (NP with a $\Sigma_i^P$ oracle)
- $\Pi_{i+1}^P = co\Sigma_{i+1}^P$ (complement of $\Sigma_{i+1}^P$)
- $\Delta_{i+1}^P = P^{\Sigma_i^P}$ (P with a $\Sigma_i^P$ oracle)

An oracle machine is a Turing machine with access to an "oracle" that can solve a specific decision problem in a single step. For a complexity class $C$, $NP^C$ represents the class of languages decidable by a non-deterministic polynomial-time Turing machine with an oracle for a language in $C$. Similarly, $P^C$ represents the class of languages decidable by a deterministic polynomial-time Turing machine with an oracle for a language in $C$.

The polynomial hierarchy is the union of all these classes: \[PH = \bigcup_{i=0}^{\infty} \Sigma_i^P = \bigcup_{i=0}^{\infty} \Pi_i^P = \bigcup_{i=0}^{\infty} \Delta_i^P\]

Alternative Definition using Certificates

The polynomial hierarchy can also be defined using the concept of certificates. Recall that a language $L$ is in NP if and only if there exists a polynomially balanced and polynomially decidable relation $R$ such that: \[x \in L \iff \exists y : |y| \leq p(|x|) \land (x, y) \in R\] where $p(|x|)$ is a polynomial bounding the length of the certificate $y$.

Definition 1 ($\Sigma_i^P$). A language $L$ belongs to the class $\Sigma_i^P$ if and only if there exists a polynomially balanced and polynomially decidable relation $R$ and a polynomial $p$ such that: \[x \in L \iff \exists y_1 \forall y_2 \dots Q_i y_i : (|y_1| \leq p(|x|), |y_2| \leq p(|x|), \dots, |y_i| \leq p(|x|) \land (x, y_1, y_2, \dots, y_i) \in R)\] where $Q_i$ is $\exists$ if $i$ is odd and $\forall$ if $i$ is even.

Definition 2 ($\Pi_i^P$). A language $L$ belongs to the class $\Pi_i^P$ if and only if there exists a polynomially balanced and polynomially decidable relation $R$ and a polynomial $p$ such that: \[x \in L \iff \forall y_1 \exists y_2 \dots Q_i y_i : (|y_1| \leq p(|x|), |y_2| \leq p(|x|), \dots, |y_i| \leq p(|x|) \land (x, y_1, y_2, \dots, y_i) \in R)\] where $Q_i$ is $\forall$ if $i$ is odd and $\exists$ if $i$ is even.

Example 1 (Characterization of $\Sigma_2^P$). A language $L$ belongs to the class $\Sigma_2^P$ if and only if there exists a polynomially balanced and polynomially decidable relation $R$ and a polynomial $p$ such that: \[x \in L \iff \exists y_1 \forall y_2 : (|y_1| \leq p(|x|), |y_2| \leq p(|x|) \land (x, y_1, y_2) \in R)\]

Note: The oracle definition and the certificate-based definition of the polynomial hierarchy are equivalent. The proof of this equivalence is beyond the scope of this lecture, but it can be shown by constructing an oracle machine that simulates the quantifiers in the certificate definition and vice-versa.

Properties of the Polynomial Hierarchy

The following properties hold for the polynomial hierarchy:

Inclusion: For all $i \geq 0$, $\Sigma_i^P \subseteq \Delta_{i+1}^P \subseteq \Sigma_{i+1}^P$ and $\Pi_i^P \subseteq \Delta_{i+1}^P \subseteq \Pi_{i+1}^P$.
Duality: For all $i \geq 0$, $\Pi_i^P = co\Sigma_i^P$ (and equivalently, $\Sigma_i^P = co\Pi_i^P$).

Alternative Notations

An alternative notation for defining the polynomial hierarchy uses the quantifiers $\exists$ and $\forall$ applied to complexity classes.

$\exists C$: For a complexity class $C$, $\exists C$ is the class of languages $L$ such that there exists a language $L' \in C$ and a polynomial $p$ with $x \in L \iff \exists y : |y| \leq p(|x|) \land (x, y) \in L'$.
$\forall C$: For a complexity class $C$, $\forall C$ is the class of languages $L$ such that there exists a language $L' \in C$ and a polynomial $p$ with $x \in L \iff \forall y : |y| \leq p(|x|) \land (x, y) \in L'$.

Using this notation, we can express the following relationships:

$NP = \exists P$
$coNP = \forall P$
$\Sigma_{i+1}^P = \exists \Pi_i^P$
$\Pi_{i+1}^P = \forall \Sigma_i^P$

These relationships provide a concise way to define the levels of the polynomial hierarchy using the $\exists$ and $\forall$ operators.

Quantified Boolean Formulas

A quantified Boolean formula (QBF) is a generalization of a Boolean formula where variables can be universally ($\forall$) or existentially ($\exists$) quantified.

Definition 3 (Quantified Boolean Formula). A quantified Boolean formula (QBF) is a formula of the form: \[Q_1 z_1 Q_2 z_2 \dots Q_n z_n \phi(z_1, z_2, \dots, z_n)\] where each $Q_i \in \{\forall, \exists\}$, $z_i$ represents a set of Boolean variables, and $\phi$ is a Boolean formula over the variables $z_1, z_2, \dots, z_n$. The variables in the sets $z_1, \dots, z_n$ are assumed to be distinct.

Example 2. Consider the Boolean formula $\phi(z_1, z_2, z_3) = (z_1 \lor \neg z_2) \land (\neg z_1 \lor z_3)$. A possible QBF using $\phi$ is: \[\exists z_1 \forall z_2 \exists z_3 \phi(z_1, z_2, z_3)\] Here, $z_1$ and $z_3$ are existentially quantified, while $z_2$ is universally quantified. Another example could be: \[\forall z_1 \forall z_2 \forall z_3 \phi(z_1, z_2, z_3)\] where all variables are universally quantified.

Semantics of QBFs

The semantics of a QBF are defined recursively based on the structure of the formula:

If the formula is of the form $\exists z_1 \psi(z_1, \dots)$, it is true if there exists a truth assignment for $z_1$ such that $\psi(z_1, \dots)$ is true.
If the formula is of the form $\forall z_1 \psi(z_1, \dots)$, it is true if for all truth assignments for $z_1$, $\psi(z_1, \dots)$ is true.
If the formula is of the form $\phi(z_1, \dots, z_n)$ (no quantifiers), it is true based on the standard semantics of propositional logic.

Example: Expanding a QBF

Let’s consider the QBF $\exists z_1 \forall z_2 \phi(z_1, z_2, z_3)$, where $\phi(z_1, z_2, z_3) = (z_1 \lor \neg z_2) \land (\neg z_1 \lor z_3)$. We can expand this QBF as follows:

Substitute $z_1$: Since $z_1$ is existentially quantified, we consider both possible values for $z_1$ (0 and 1): \[\forall z_2 \phi(0, z_2, z_3) \lor \forall z_2 \phi(1, z_2, z_3)\]
Substitute $z_2$: Now, $z_2$ is universally quantified, so we need to consider both values for $z_2$ in each part of the disjunction: \[[\phi(0, 0, z_3) \land \phi(0, 1, z_3)] \lor [\phi(1, 0, z_3) \land \phi(1, 1, z_3)]\]
Evaluate $\phi$: Finally, we can substitute the values into $\phi$ to get a formula with only $z_3$ as a free variable: \[[(0 \lor \neg 0) \land (\neg 0 \lor z_3)] \land [(0 \lor \neg 1) \land (\neg 0 \lor z_3)] \lor [(1 \lor \neg 0) \land (\neg 1 \lor z_3)] \land [(1 \lor \neg 1) \land (\neg 1 \lor z_3)]\] \[[(1 \land (1 \lor z_3)) \land (1 \land (1 \lor z_3))] \lor [(1 \land (0 \lor z_3)) \land (1 \land (0 \lor z_3))]\] \[(1 \land 1) \lor (z_3 \land z_3)\] \[1 \lor z_3\]

The resulting formula is $1 \lor z_3$, which is always true regardless of the value of $z_3$. Therefore, the original QBF $\exists z_1 \forall z_2 \phi(z_1, z_2, z_3)$ is true.

$\Sigma_i$-SAT and $\Pi_i$-SAT

We define two important families of decision problems related to QBFs:

Definition 4 ($\Sigma_i$-SAT). $\Sigma_i$-SAT is the problem of deciding whether a given QBF of the form \[\exists Y_1 \forall Y_2 \exists Y_3 \dots Q_i Y_i \ \phi(Y_1, Y_2, \dots, Y_i)\] is true, where $Y_j$ are sets of variables, $\phi$ is a Boolean formula, and $Q_i$ is $\exists$ if $i$ is odd and $\forall$ if $i$ is even.

Definition 5 ($\Pi_i$-SAT). $\Pi_i$-SAT is the problem of deciding whether a given QBF of the form \[\forall Y_1 \exists Y_2 \forall Y_3 \dots Q_i Y_i \ \phi(Y_1, Y_2, \dots, Y_i)\] is true, where $Y_j$ are sets of variables, $\phi$ is a Boolean formula, and $Q_i$ is $\forall$ if $i$ is odd and $\exists$ if $i$ is even.

Theorem 1 (Completeness of $\Sigma_i$-SAT and $\Pi_i$-SAT). For every $i \geq 1$, $\Sigma_i$-SAT is $\Sigma_i^P$-complete, and $\Pi_i$-SAT is $\Pi_i^P$-complete.

This theorem establishes the close connection between QBFs and the polynomial hierarchy. It shows that the problem of deciding the truth of a QBF with a specific quantifier alternation pattern is complete for the corresponding level of the polynomial hierarchy. Moreover, it implies that $\Sigma_i\text{-SAT} \in \Sigma_i^P$ and $\Pi_i\text{-SAT} \in \Pi_i^P$.

Collapse of the Polynomial Hierarchy

A fundamental question about the polynomial hierarchy is whether it is a strict hierarchy (i.e., each level is distinct) or whether it collapses to some finite level.

Definition 6 (Collapse). The polynomial hierarchy collapses to level $i$ if $\Sigma_i^P = \Sigma_{i+1}^P$ (or equivalently, if $\Pi_i^P = \Pi_{i+1}^P$).

If the polynomial hierarchy collapses to level $i$, it implies that $\Sigma_i^P = \Sigma_j^P$ for all $j > i$, and consequently, $PH = \Sigma_i^P$. In other words, the entire hierarchy collapses to a single level.

Theorem 2 (Collapse of the Polynomial Hierarchy). If there exists an $i$ such that $\Sigma_i^P = \Sigma_{i+1}^P$, then $PH = \Sigma_i^P$. Equivalently, if there exists an $i$ such that $\Pi_i^P = \Pi_{i+1}^P$, then $PH = \Pi_i^P$.

Proof. Proof. We will prove this by induction.

Base Case: If $\Sigma_i^P = \Sigma_{i+1}^P$, then $\Pi_i^P = co\Sigma_i^P = co\Sigma_{i+1}^P = \Pi_{i+1}^P$.

Inductive Step: Assume that $\Sigma_i^P = \Sigma_{i+k}^P$ for some $k \geq 1$. We want to show that $\Sigma_i^P = \Sigma_{i+k+1}^P$. By definition, $\Sigma_{i+k+1}^P = NP^{\Sigma_{i+k}^P}$. By the inductive hypothesis, $\Sigma_{i+k}^P = \Sigma_i^P$, so $\Sigma_{i+k+1}^P = NP^{\Sigma_i^P}$. Since $\Sigma_i^P = \Sigma_{i+1}^P$, we have $\Sigma_{i+k+1}^P = NP^{\Sigma_{i}^P} = \Sigma_{i+1}^P = \Sigma_i^P$.

Therefore, if $\Sigma_i^P = \Sigma_{i+1}^P$, then $\Sigma_i^P = \Sigma_j^P$ for all $j \geq i$. Consequently, $PH = \bigcup_{j=0}^{\infty} \Sigma_j^P = \Sigma_i^P$. The proof for the $\Pi_i^P$ case is analogous. ◻

Remark. Remark 1. It is an open problem whether there exists an index $i$ such that $\Sigma_i^P = \Sigma_{i+1}^P$. In other words, it is unknown whether the polynomial hierarchy collapses.

Remark. Remark 2. Most researchers believe that the polynomial hierarchy does not collapse, meaning that all levels are distinct. However, proving this conjecture remains a major challenge in complexity theory.

If the polynomial hierarchy were to collapse, it would have significant implications for the relationships between complexity classes. For example, if $P = NP$ (i.e., $\Sigma_0^P = \Sigma_1^P$), then the polynomial hierarchy would collapse to $P$. The collapse of the polynomial hierarchy at higher levels is considered less likely but would still be a surprising result. It is also known that if $PH = PSPACE$, then the polynomial hierarchy collapses to a finite level.

Theorem 3 (Relationship between PH and PSPACE). If $PH = PSPACE$, then there exists a $k$ such that $PH = \Sigma_k^P$.

This theorem states that if the polynomial hierarchy equals PSPACE, then the hierarchy collapses to a finite level.

Trace Equivalence and Bisimulation

In this section, we will explore two important notions of equivalence between systems, particularly in the context of automata: trace equivalence and bisimulation. These concepts are fundamental in the field of system verification, where we aim to determine if two systems are equivalent in some sense.

Graph Isomorphism and Bisimulation

Graph Isomorphism: Two graphs are isomorphic if there exists a bijection between their vertices that preserves adjacency. This is a structural equivalence notion that compares graphs from an "external" perspective, looking at their overall structure.
Graph Bisimulation: Bisimulation is a more refined notion of equivalence that considers the "behavior" of the graphs. It compares graphs from an "internal" perspective, simulating steps within the graphs. Informally, two states are bisimilar if they can mimic each other’s behavior step by step.

Definition 7 (Trace Equivalence). Let $A_1 = (S_1, \Sigma, \rightarrow_1, I_1)$ and $A_2 = (S_2, \Sigma, \rightarrow_2, I_2)$ be two automata, where $S_i$ is the set of states, $\Sigma$ is the alphabet, $\rightarrow_i \subseteq S_i \times \Sigma \times S_i$ is the transition relation, and $I_i \subseteq S_i$ is the set of initial states for $i \in \{1, 2\}$. A trace of an automaton is a sequence of labels corresponding to a path starting from an initial state. The language of an automaton $A$, denoted by $L(A)$, is the set of all its traces.

$A_1$ and $A_2$ are trace equivalent if their languages are the same, i.e., $L(A_1) = L(A_2)$.

Definition 8 (Bisimulation). Let $A_1 = (S_1, \Sigma, \rightarrow_1, I_1)$ and $A_2 = (S_2, \Sigma, \rightarrow_2, I_2)$ be two automata. A bisimulation between $A_1$ and $A_2$ is a relation $R \subseteq S_1 \times S_2$ such that:

For every initial state $s_1 \in I_1$, there exists an initial state $s_2 \in I_2$ such that $(s_1, s_2) \in R$.
For every initial state $s_2 \in I_2$, there exists an initial state $s_1 \in I_1$ such that $(s_1, s_2) \in R$.
If $(s_1, s_2) \in R$ and $s_1 \xrightarrow{a}_1 s'_1$ for some $a \in \Sigma$, then there exists a state $s'_2 \in S_2$ such that $s_2 \xrightarrow{a}_2 s'_2$ and $(s'_1, s'_2) \in R$.
If $(s_1, s_2) \in R$ and $s_2 \xrightarrow{a}_2 s'_2$ for some $a \in \Sigma$, then there exists a state $s'_1 \in S_1$ such that $s_1 \xrightarrow{a}_1 s'_1$ and $(s'_1, s'_2) \in R$.

$A_1$ and $A_2$ are bisimilar if there exists a bisimulation $R$ between them such that for every initial state in $A_1$ there is a related initial state in $A_2$, and vice-versa.

Bisimulation is a stronger notion of equivalence than trace equivalence. If two automata are bisimilar, they are also trace equivalent, but the converse is not necessarily true.

Example: Coffee Machine vs. Insurance Contract

Consider two scenarios represented by automata:

Coffee Machine:
- Automaton 1: Decide (tea or coffee) before inserting a coin.
- Automaton 2: Insert a coin, then decide (tea or coffee).
Insurance Contract:
- Automaton 1: Decide (cash or monthly payment) before paying.
- Automaton 2: Pay, then decide (cash or monthly payment).

Two automata representing different coffee machines or insurance contracts.

In both cases, the automata representing the two scenarios are trace equivalent because they recognize the same language: $L(A_1) = L(A_2) = \{\text{coin.tea}, \text{coin.coffee}\}$. However, they are not bisimilar.

Intuition: - If you are in the initial state of $A_2$ and your friend is in the initial state of $A_1$, your friend can put aThe user wants me to continue the LaTeX document. I stopped mid-sentence while explaining the intuition behind the coffee machine and insurance contract example. I need to complete that sentence and then proceed with the rest of the document, applying the requested formatting with ‘tcolorbox’.If you are in the initial state of $A_2$ and your friend is in the initial state of $A_1$, your friend can put a coin and move to the next state. You can also put a coin and move to the next state. - Now, if your friend chooses "tea", you cannot simulate it because you are in a state where you must choose "tea" or "coffee" after putting a coin. - Therefore, there is no bisimulation relation between the initial states of $A_1$ and $A_2$.

In the coffee machine scenario, the difference might be negligible. But in the insurance contract scenario, the difference is crucial: deciding upfront vs. deciding later can have vastly different consequences.

LTL and CTL

LTL (Linear Temporal Logic): LTL formulas are interpreted over traces (sequences of states). LTL cannot distinguish between trace equivalent automata. If two automata are trace equivalent, they satisfy the same set of LTL formulas.
CTL (Computation Tree Logic): CTL formulas are interpreted over computation trees. CTL can distinguish between bisimilar automata. If two automata are not bisimilar, there might be a CTL formula that is true in one but false in the other.

The choice between trace equivalence and bisimulation depends on the specific application and the desired level of granularity in distinguishing between systems. Trace equivalence is a coarser notion, suitable when only the observable sequences of actions matter. Bisimulation is finer-grained, capable of distinguishing systems with different branching behaviors. The complexity of deciding trace equivalence is PSPACE-complete, while the complexity of deciding bisimulation is in P.

Complexity Classes: PSPACE, EXP, and NEXP

This section introduces three important complexity classes beyond P and NP:PSPACE, EXP, and NEXP. These classes help us understand the limits of computation in terms of space and time.

PSPACE: The class of languages decidable by a deterministic Turing machine using a polynomial amount of space. Formally, \[PSPACE = \bigcup_{k=1}^{\infty} SPACE(n^k)\] where $SPACE(n^k)$ denotes the set of languages decidable by a deterministic Turing machine using at most $n^k$ space for an input of length $n$.
EXP (EXPTIME): The class of languages decidable by a deterministic Turing machine in exponential time. Formally, \[EXP = \bigcup_{k=1}^{\infty} TIME(2^{n^k})\] where $TIME(2^{n^k})$ denotes the set of languages decidable by a deterministic Turing machine in at most $2^{n^k}$ time for an input of length $n$.
NEXP (NEXPTIME): The class of languages decidable by a non-deterministic Turing machine in exponential time. Formally, \[NEXP = \bigcup_{k=1}^{\infty} NTIME(2^{n^k})\] where $NTIME(2^{n^k})$ denotes the set of languages decidable by a non-deterministic Turing machine in at most $2^{n^k}$ time for an input of length $n$.

Relationship between complexity classes

It is known that $P \subseteq NP \subseteq PSPACE \subseteq EXP \subseteq NEXP$, and also that $P \subsetneq EXP$ and $NP \subsetneq NEXP$. However, it is unknown whether $P = NP$, $NP = PSPACE$, $PSPACE = EXP$, or $EXP = NEXP$.

Theorem 4 (If P=NP then EXP=NEXP). If $P = NP$, then $EXP = NEXP$.

Proof. Proof. Proof Idea (Padding Technique): The proof uses a technique called padding. The main idea is to take a language $L$ in NEXP and transform it into a related language $L'$ in NP by adding a large number of "padding" symbols to the input. If $P = NP$, then $L'$ can be decided in P, and this can be used to decide the original language $L$ in EXP.

Let $L \in NEXP$. Then there exists a non-deterministic Turing machine $M$ that decides $L$ in time $2^{n^k}$ for some constant $k$.

Define a new language $L'$ (the padded version of $L$) as follows: \[L' = \{ x\#^{2^{|x|^k} - |x|} : x \in L \}\] where $\#$ is a special symbol not in the alphabet of $L$. The length of the padding is such that the total length of the input string in $L'$ is $2^{|x|^k}$.

Since $M$ decides $L$ in time $2^{n^k}$, we can construct a non-deterministic Turing machine $M'$ that decides $L'$ in time linear to its input length. $M'$ on input $y$ first checks if $y$ is of the form $x\#^{2^{|x|^k} - |x|}$. If not, it rejects. Otherwise, it simulates $M$ on $x$ for $|y|$ steps. If $M$ accepts within $|y|$ steps, $M'$ accepts; otherwise, $M'$ rejects.

Thus, $L' \in NP$. If $P = NP$, then $L' \in P$. This means there exists a deterministic Turing machine $D$ that decides $L'$ in polynomial time, say $p(n)$.

Now we can construct a deterministic Turing machine $D'$ that decides $L$ in exponential time. $D'$ on input $x$ constructs the string $x\#^{2^{|x|^k} - |x|}$ and simulates $D$ on this string. $D'$ accepts if $D$ accepts, and rejects otherwise. The runtime of $D'$ is dominated by the time to construct the padded string, which is $O(2^{|x|^k})$, and the time to simulate $D$, which is $p(2^{|x|^k})$. Thus, $D'$ runs in exponential time, and $L \in EXP$. Since $L$ was an arbitrary language in $NEXP$, we have $NEXP \subseteq EXP$. The other direction, $EXP \subseteq NEXP$ is trivial.

Therefore, if $P = NP$, then $EXP = NEXP$. ◻

Succinct Problems

The concept of succinctness introduces a way to represent instances of problems in a more compact form, often leading to higher complexity. Instead of explicitly providing the entire input, a succinct representation provides a smaller, encoded version of the input that can be expanded to obtain the original input.

Circuit Value Problem (CVP): Given a Boolean circuit with no inputs (only constant gates) and a designated output gate, determine the output value of the circuit. CVP is P-complete.
Circuit Satisfiability Problem (Circuit SAT): Given a Boolean circuit with inputs, determine if there exists an assignment to the inputs that makes the output true. Circuit SAT is NP-complete.
Succinct Circuit Value Problem (Succinct CVP): Given a succinct representation of a Boolean circuit (i.e., another circuit that implicitly describes the circuit), determine the output value of the implicitly described circuit. Succinct CVP is EXP-complete.
Succinct Circuit Satisfiability Problem (Succinct Circuit SAT): Given a succinct representation of a Boolean circuit, determine if there exists an assignment to the inputs of the implicitly described circuit that makes the output true. Succinct Circuit SAT is NEXP-complete.

Definition 9 (Succinct Representation). In succinct versions of problems, the input is not given explicitly but is represented implicitly by a smaller, "meta" circuit. This meta-circuit, when evaluated, describes the actual input circuit for the problem. More formally, the succinct representation of a circuit $C$ is another circuit $C_{meta}$ such that $C_{meta}(i, j)$ outputs the type of gate $i$ and whether gate $i$ is connected to gate $j$ in the circuit $C$.

For example, in Succinct CVP, instead of being given the entire circuit directly, you are given a smaller circuit that, when evaluated, generates the description of the larger circuit whose value you need to determine. This implicit representation makes the problem exponentially harder.

The succinct versions of these problems highlight how the way a problem instance is represented can significantly impact its complexity. They demonstrate that a compact representation can encode an exponentially larger structure, leading to an exponential increase in the computational resources required to solve the problem.

Conclusion

This lecture provided a comprehensive overview of the polynomial hierarchy (PH), a fundamental concept in computational complexity theory. We began by defining the PH using both oracle machines and certificates, establishing the groundwork for understanding its structure and properties. We then introduced quantified Boolean formulas (QBFs) as a powerful tool for characterizing the complexity classes within the PH, culminating in the definitions of $\Sigma_i$-SAT and $\Pi_i$-SAT and their respective completeness results.

A significant portion of the lecture was dedicated to the intriguing question of whether the polynomial hierarchy collapses. We explored the implications of such a collapse and highlighted the prevailing conjecture that the hierarchy is, in fact, strict. We proved that if the hierarchy collapses at any level, it collapses to that level.

Furthermore, we delved into the realm of system verification by examining trace equivalence and bisimulation, two distinct notions of equivalence between automata. The example of coffee machines and insurance contracts illustrated the practical differences between these concepts and why choosing the right notion of equivalence is crucial in different scenarios. We also saw how Linear Temporal Logic (LTL) and Computation Tree Logic (CTL) relate to trace equivalence and bisimulation, respectively, providing a crucial link between theoretical models and verification techniques.

Finally, we expanded our complexity landscape by introducing PSPACE, EXP, and NEXP, showcasing their relationships with the polynomial hierarchy. We discussed the padding technique for proving that if $P=NP$ then $EXP=NEXP$. The concept of succinctness was introduced through succinct versions of the circuit value and circuit satisfiability problems, demonstrating how compact representations can lead to increased complexity.

The polynomial hierarchy provides a framework for classifying problems based on their complexity beyond NP and coNP.
QBFs offer a powerful way to define and understand the levels of the polynomial hierarchy.
The collapse of the PH remains a major open problem with significant implications.
Trace equivalence and bisimulation are crucial concepts in system verification, each with its own strengths and weaknesses. Trace equivalence is a coarser notion than bisimulation and is related to LTL, while bisimulation is related to CTL.
Succinct representations can dramatically increase the complexity of problems by encoding an exponentially larger structure in a compact form.

Follow-up Questions:

The following questions represent exciting avenues for further exploration and research:

Equivalence of Definitions: Can we formally prove the equivalence between the oracle-based and certificate-based definitions of the polynomial hierarchy? This would solidify the foundations of the PH.
Implications of Collapse: What are the precise implications of the polynomial hierarchy collapsing at a specific level $i$? How would this affect the relationships between other complexity classes and the solvability of certain problems?
LTL vs. CTL: How can we determine the most appropriate temporal logic (LTL or CTL) for a given system verification task? What are the trade-offs between expressiveness and computational complexity?
Succinctness and Complexity: How does succinctness affect the complexity of other problems beyond circuit value and satisfiability? Can we develop general techniques for analyzing the complexity of succinctly represented problems?
Beyond PH: Are there other meaningful hierarchies beyond the polynomial hierarchy that can help us better understand the landscape of computational complexity?

These questions highlight the ongoing research and open problems in complexity theory and system verification, underscoring the depth and richness of these fields. They encourage further investigation into the nature of computation and the limits of what can be efficiently computed.

--- title: "Lecture Notes: Polynomial Hierarchy and Related Concepts" author: "Your Name" date: "2025-01-28" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture delves into the intricacies of the **polynomial hierarchy (PH)**, exploring its various facets, including alternative definitions and connections to other complexity classes. We will investigate the crucial role of **certificates** in defining complexity classes within the PH. Furthermore, the concept of **quantified Boolean formulas** will be introduced, providing a powerful tool for understanding and characterizing these classes. The lecture will also cover the relationship between the polynomial hierarchy and other important complexity classes such as **PSPACE**, **EXP**, and **NEXP**. In addition to the theoretical foundations, we will bridge the gap between abstract concepts and practical applications by examining **trace equivalence** and **bisimulation** in the context of automata. We will use an example involving a coffee machine and an insurance contract to illustrate the differences between these two concepts and how they relate to system verification. This will shed light on how these notions are employed in the crucial field of **system verification** and why choosing the correct notion of equivalence is critical. Finally, we will briefly discuss the concept of succinct circuit representation and its impact on the complexity of circuit problems. ::: tcolorbox - Polynomial Hierarchy (PH) and its alternative definitions - Certificates and their role in defining complexity classes - Quantified Boolean Formulas - Complexity Classes: PSPACE, EXP, NEXP - Trace Equivalence and Bisimulation in Automata - Applications in System Verification - Succinct Circuit Representation ::: The lecture will use illustrative examples and connect theoretical concepts to practical applications in system verification. The concepts introduced in this lecture are fundamental for understanding the landscape of computational complexity and its implications in various domains. # Polynomial Hierarchy ## Definition using Oracles The polynomial hierarchy (PH) is a hierarchy of complexity classes that generalizes the classes NP and coNP. It is defined recursively using the concept of **oracle machines**. - **Base Case:** - $\Sigma_0^P = \Pi_0^P = \Delta_0^P = P$ - $\Sigma_1^P = NP$ - $\Pi_1^P = coNP$ - $\Delta_1^P = P$ - **Inductive Step:** For $i \geq 1$ - $\Sigma_{i+1}^P = NP^{\Sigma_i^P}$ (NP with a $\Sigma_i^P$ oracle) - $\Pi_{i+1}^P = co\Sigma_{i+1}^P$ (complement of $\Sigma_{i+1}^P$) - $\Delta_{i+1}^P = P^{\Sigma_i^P}$ (P with a $\Sigma_i^P$ oracle) ::: tcolorbox An oracle machine is a Turing machine with access to an \"oracle\" that can solve a specific decision problem in a single step. For a complexity class $C$, $NP^C$ represents the class of languages decidable by a non-deterministic polynomial-time Turing machine with an oracle for a language in $C$. Similarly, $P^C$ represents the class of languages decidable by a deterministic polynomial-time Turing machine with an oracle for a language in $C$. ::: The polynomial hierarchy is the union of all these classes: $$PH = \bigcup_{i=0}^{\infty} \Sigma_i^P = \bigcup_{i=0}^{\infty} \Pi_i^P = \bigcup_{i=0}^{\infty} \Delta_i^P$$ ::: center ::: ## Alternative Definition using Certificates The polynomial hierarchy can also be defined using the concept of **certificates**. Recall that a language $L$ is in NP if and only if there exists a polynomially balanced and polynomially decidable relation $R$ such that: $$x \in L \iff \exists y : |y| \leq p(|x|) \land (x, y) \in R$$ where $p(|x|)$ is a polynomial bounding the length of the certificate $y$. :::: tcolorbox ::: definition **Definition 1** ($\Sigma_i^P$). *A language $L$ belongs to the class $\Sigma_i^P$ if and only if there exists a polynomially balanced and polynomially decidable relation $R$ and a polynomial $p$ such that: $$x \in L \iff \exists y_1 \forall y_2 \dots Q_i y_i : (|y_1| \leq p(|x|), |y_2| \leq p(|x|), \dots, |y_i| \leq p(|x|) \land (x, y_1, y_2, \dots, y_i) \in R)$$ where $Q_i$ is $\exists$ if $i$ is odd and $\forall$ if $i$ is even.* ::: :::: :::: tcolorbox ::: definition **Definition 2** ($\Pi_i^P$). *A language $L$ belongs to the class $\Pi_i^P$ if and only if there exists a polynomially balanced and polynomially decidable relation $R$ and a polynomial $p$ such that: $$x \in L \iff \forall y_1 \exists y_2 \dots Q_i y_i : (|y_1| \leq p(|x|), |y_2| \leq p(|x|), \dots, |y_i| \leq p(|x|) \land (x, y_1, y_2, \dots, y_i) \in R)$$ where $Q_i$ is $\forall$ if $i$ is odd and $\exists$ if $i$ is even.* ::: :::: :::: tcolorbox ::: example **Example 1** (Characterization of $\Sigma_2^P$). *A language $L$ belongs to the class $\Sigma_2^P$ if and only if there exists a polynomially balanced and polynomially decidable relation $R$ and a polynomial $p$ such that: $$x \in L \iff \exists y_1 \forall y_2 : (|y_1| \leq p(|x|), |y_2| \leq p(|x|) \land (x, y_1, y_2) \in R)$$* ::: :::: **Note:** The oracle definition and the certificate-based definition of the polynomial hierarchy are equivalent. The proof of this equivalence is beyond the scope of this lecture, but it can be shown by constructing an oracle machine that simulates the quantifiers in the certificate definition and vice-versa. ## Properties of the Polynomial Hierarchy The following properties hold for the polynomial hierarchy: 1. **Inclusion:** For all $i \geq 0$, $\Sigma_i^P \subseteq \Delta_{i+1}^P \subseteq \Sigma_{i+1}^P$ and $\Pi_i^P \subseteq \Delta_{i+1}^P \subseteq \Pi_{i+1}^P$. 2. **Duality:** For all $i \geq 0$, $\Pi_i^P = co\Sigma_i^P$ (and equivalently, $\Sigma_i^P = co\Pi_i^P$). ## Alternative Notations An alternative notation for defining the polynomial hierarchy uses the quantifiers $\exists$ and $\forall$ applied to complexity classes. - $\exists C$: For a complexity class $C$, $\exists C$ is the class of languages $L$ such that there exists a language $L' \in C$ and a polynomial $p$ with $x \in L \iff \exists y : |y| \leq p(|x|) \land (x, y) \in L'$. - $\forall C$: For a complexity class $C$, $\forall C$ is the class of languages $L$ such that there exists a language $L' \in C$ and a polynomial $p$ with $x \in L \iff \forall y : |y| \leq p(|x|) \land (x, y) \in L'$. Using this notation, we can express the following relationships: - $NP = \exists P$ - $coNP = \forall P$ - $\Sigma_{i+1}^P = \exists \Pi_i^P$ - $\Pi_{i+1}^P = \forall \Sigma_i^P$ These relationships provide a concise way to define the levels of the polynomial hierarchy using the $\exists$ and $\forall$ operators. # Quantified Boolean Formulas A **quantified Boolean formula (QBF)** is a generalization of a Boolean formula where variables can be universally ($\forall$) or existentially ($\exists$) quantified. :::: tcolorbox ::: definition **Definition 3** (Quantified Boolean Formula). *A quantified Boolean formula (QBF) is a formula of the form: $$Q_1 z_1 Q_2 z_2 \dots Q_n z_n \phi(z_1, z_2, \dots, z_n)$$ where each $Q_i \in \{\forall, \exists\}$, $z_i$ represents a set of Boolean variables, and $\phi$ is a Boolean formula over the variables $z_1, z_2, \dots, z_n$. The variables in the sets $z_1, \dots, z_n$ are assumed to be distinct.* ::: :::: :::: tcolorbox ::: example **Example 2**. *Consider the Boolean formula $\phi(z_1, z_2, z_3) = (z_1 \lor \neg z_2) \land (\neg z_1 \lor z_3)$. A possible QBF using $\phi$ is: $$\exists z_1 \forall z_2 \exists z_3 \phi(z_1, z_2, z_3)$$ Here, $z_1$ and $z_3$ are existentially quantified, while $z_2$ is universally quantified. Another example could be: $$\forall z_1 \forall z_2 \forall z_3 \phi(z_1, z_2, z_3)$$ where all variables are universally quantified.* ::: :::: ## Semantics of QBFs The semantics of a QBF are defined recursively based on the structure of the formula: - If the formula is of the form $\exists z_1 \psi(z_1, \dots)$, it is true if there exists a truth assignment for $z_1$ such that $\psi(z_1, \dots)$ is true. - If the formula is of the form $\forall z_1 \psi(z_1, \dots)$, it is true if for all truth assignments for $z_1$, $\psi(z_1, \dots)$ is true. - If the formula is of the form $\phi(z_1, \dots, z_n)$ (no quantifiers), it is true based on the standard semantics of propositional logic. ## Example: Expanding a QBF Let's consider the QBF $\exists z_1 \forall z_2 \phi(z_1, z_2, z_3)$, where $\phi(z_1, z_2, z_3) = (z_1 \lor \neg z_2) \land (\neg z_1 \lor z_3)$. We can expand this QBF as follows: 1. **Substitute $z_1$:** Since $z_1$ is existentially quantified, we consider both possible values for $z_1$ (0 and 1): $$\forall z_2 \phi(0, z_2, z_3) \lor \forall z_2 \phi(1, z_2, z_3)$$ 2. **Substitute $z_2$:** Now, $z_2$ is universally quantified, so we need to consider both values for $z_2$ in each part of the disjunction: $$[\phi(0, 0, z_3) \land \phi(0, 1, z_3)] \lor [\phi(1, 0, z_3) \land \phi(1, 1, z_3)]$$ 3. **Evaluate $\phi$:** Finally, we can substitute the values into $\phi$ to get a formula with only $z_3$ as a free variable: $$[(0 \lor \neg 0) \land (\neg 0 \lor z_3)] \land [(0 \lor \neg 1) \land (\neg 0 \lor z_3)] \lor [(1 \lor \neg 0) \land (\neg 1 \lor z_3)] \land [(1 \lor \neg 1) \land (\neg 1 \lor z_3)]$$ $$[(1 \land (1 \lor z_3)) \land (1 \land (1 \lor z_3))] \lor [(1 \land (0 \lor z_3)) \land (1 \land (0 \lor z_3))]$$ $$(1 \land 1) \lor (z_3 \land z_3)$$ $$1 \lor z_3$$ The resulting formula is $1 \lor z_3$, which is always true regardless of the value of $z_3$. Therefore, the original QBF $\exists z_1 \forall z_2 \phi(z_1, z_2, z_3)$ is true. ## $\Sigma_i$-SAT and $\Pi_i$-SAT We define two important families of decision problems related to QBFs: :::: tcolorbox ::: definition **Definition 4** ($\Sigma_i$-SAT). *$\Sigma_i$-SAT is the problem of deciding whether a given QBF of the form $$\exists Y_1 \forall Y_2 \exists Y_3 \dots Q_i Y_i \ \phi(Y_1, Y_2, \dots, Y_i)$$ is true, where $Y_j$ are sets of variables, $\phi$ is a Boolean formula, and $Q_i$ is $\exists$ if $i$ is odd and $\forall$ if $i$ is even.* ::: :::: :::: tcolorbox ::: definition **Definition 5** ($\Pi_i$-SAT). *$\Pi_i$-SAT is the problem of deciding whether a given QBF of the form $$\forall Y_1 \exists Y_2 \forall Y_3 \dots Q_i Y_i \ \phi(Y_1, Y_2, \dots, Y_i)$$ is true, where $Y_j$ are sets of variables, $\phi$ is a Boolean formula, and $Q_i$ is $\forall$ if $i$ is odd and $\exists$ if $i$ is even.* ::: :::: :::: tcolorbox ::: theorem **Theorem 1** (Completeness of $\Sigma_i$-SAT and $\Pi_i$-SAT). *For every $i \geq 1$, $\Sigma_i$-SAT is $\Sigma_i^P$-complete, and $\Pi_i$-SAT is $\Pi_i^P$-complete.* ::: :::: This theorem establishes the close connection between QBFs and the polynomial hierarchy. It shows that the problem of deciding the truth of a QBF with a specific quantifier alternation pattern is complete for the corresponding level of the polynomial hierarchy. Moreover, it implies that $\Sigma_i\text{-SAT} \in \Sigma_i^P$ and $\Pi_i\text{-SAT} \in \Pi_i^P$. # Collapse of the Polynomial Hierarchy A fundamental question about the polynomial hierarchy is whether it is a strict hierarchy (i.e., each level is distinct) or whether it **collapses** to some finite level. :::: tcolorbox ::: definition **Definition 6** (Collapse). *The polynomial hierarchy collapses to level $i$ if $\Sigma_i^P = \Sigma_{i+1}^P$ (or equivalently, if $\Pi_i^P = \Pi_{i+1}^P$).* ::: :::: If the polynomial hierarchy collapses to level $i$, it implies that $\Sigma_i^P = \Sigma_j^P$ for all $j > i$, and consequently, $PH = \Sigma_i^P$. In other words, the entire hierarchy collapses to a single level. :::: tcolorbox ::: theorem **Theorem 2** (Collapse of the Polynomial Hierarchy). *If there exists an $i$ such that $\Sigma_i^P = \Sigma_{i+1}^P$, then $PH = \Sigma_i^P$. Equivalently, if there exists an $i$ such that $\Pi_i^P = \Pi_{i+1}^P$, then $PH = \Pi_i^P$.* ::: :::: ::: proof *Proof.* We will prove this by induction. **Base Case:** If $\Sigma_i^P = \Sigma_{i+1}^P$, then $\Pi_i^P = co\Sigma_i^P = co\Sigma_{i+1}^P = \Pi_{i+1}^P$. **Inductive Step:** Assume that $\Sigma_i^P = \Sigma_{i+k}^P$ for some $k \geq 1$. We want to show that $\Sigma_i^P = \Sigma_{i+k+1}^P$. By definition, $\Sigma_{i+k+1}^P = NP^{\Sigma_{i+k}^P}$. By the inductive hypothesis, $\Sigma_{i+k}^P = \Sigma_i^P$, so $\Sigma_{i+k+1}^P = NP^{\Sigma_i^P}$. Since $\Sigma_i^P = \Sigma_{i+1}^P$, we have $\Sigma_{i+k+1}^P = NP^{\Sigma_{i}^P} = \Sigma_{i+1}^P = \Sigma_i^P$. Therefore, if $\Sigma_i^P = \Sigma_{i+1}^P$, then $\Sigma_i^P = \Sigma_j^P$ for all $j \geq i$. Consequently, $PH = \bigcup_{j=0}^{\infty} \Sigma_j^P = \Sigma_i^P$. The proof for the $\Pi_i^P$ case is analogous. ◻ ::: :::: tcolorbox ::: remark **Remark 1**. *It is an open problem whether there exists an index $i$ such that $\Sigma_i^P = \Sigma_{i+1}^P$. In other words, it is unknown whether the polynomial hierarchy collapses.* ::: :::: :::: tcolorbox ::: remark **Remark 2**. *Most researchers believe that the polynomial hierarchy does not collapse, meaning that all levels are distinct. However, proving this conjecture remains a major challenge in complexity theory.* ::: :::: If the polynomial hierarchy were to collapse, it would have significant implications for the relationships between complexity classes. For example, if $P = NP$ (i.e., $\Sigma_0^P = \Sigma_1^P$), then the polynomial hierarchy would collapse to $P$. The collapse of the polynomial hierarchy at higher levels is considered less likely but would still be a surprising result. It is also known that if $PH = PSPACE$, then the polynomial hierarchy collapses to a finite level. :::: tcolorbox ::: theorem **Theorem 3** (Relationship between PH and PSPACE). *If $PH = PSPACE$, then there exists a $k$ such that $PH = \Sigma_k^P$.* ::: :::: This theorem states that if the polynomial hierarchy equals PSPACE, then the hierarchy collapses to a finite level. # Trace Equivalence and Bisimulation In this section, we will explore two important notions of equivalence between systems, particularly in the context of automata: **trace equivalence** and **bisimulation**. These concepts are fundamental in the field of system verification, where we aim to determine if two systems are equivalent in some sense. ## Graph Isomorphism and Bisimulation - **Graph Isomorphism**: Two graphs are isomorphic if there exists a bijection between their vertices that preserves adjacency. This is a structural equivalence notion that compares graphs from an \"external\" perspective, looking at their overall structure. ::: center ::: - **Graph Bisimulation**: Bisimulation is a more refined notion of equivalence that considers the \"behavior\" of the graphs. It compares graphs from an \"internal\" perspective, simulating steps within the graphs. Informally, two states are bisimilar if they can mimic each other's behavior step by step. :::: tcolorbox ::: definition **Definition 7** (Trace Equivalence). *Let $A_1 = (S_1, \Sigma, \rightarrow_1, I_1)$ and $A_2 = (S_2, \Sigma, \rightarrow_2, I_2)$ be two automata, where $S_i$ is the set of states, $\Sigma$ is the alphabet, $\rightarrow_i \subseteq S_i \times \Sigma \times S_i$ is the transition relation, and $I_i \subseteq S_i$ is the set of initial states for $i \in \{1, 2\}$. A **trace** of an automaton is a sequence of labels corresponding to a path starting from an initial state. The **language** of an automaton $A$, denoted by $L(A)$, is the set of all its traces.* *$A_1$ and $A_2$ are **trace equivalent** if their languages are the same, i.e., $L(A_1) = L(A_2)$.* ::: :::: :::: tcolorbox ::: definition **Definition 8** (Bisimulation). *Let $A_1 = (S_1, \Sigma, \rightarrow_1, I_1)$ and $A_2 = (S_2, \Sigma, \rightarrow_2, I_2)$ be two automata. A **bisimulation** between $A_1$ and $A_2$ is a relation $R \subseteq S_1 \times S_2$ such that:* 1. *For every initial state $s_1 \in I_1$, there exists an initial state $s_2 \in I_2$ such that $(s_1, s_2) \in R$.* 2. *For every initial state $s_2 \in I_2$, there exists an initial state $s_1 \in I_1$ such that $(s_1, s_2) \in R$.* 3. *If $(s_1, s_2) \in R$ and $s_1 \xrightarrow{a}_1 s'_1$ for some $a \in \Sigma$, then there exists a state $s'_2 \in S_2$ such that $s_2 \xrightarrow{a}_2 s'_2$ and $(s'_1, s'_2) \in R$.* 4. *If $(s_1, s_2) \in R$ and $s_2 \xrightarrow{a}_2 s'_2$ for some $a \in \Sigma$, then there exists a state $s'_1 \in S_1$ such that $s_1 \xrightarrow{a}_1 s'_1$ and $(s'_1, s'_2) \in R$.* *$A_1$ and $A_2$ are **bisimilar** if there exists a bisimulation $R$ between them such that for every initial state in $A_1$ there is a related initial state in $A_2$, and vice-versa.* ::: :::: Bisimulation is a stronger notion of equivalence than trace equivalence. If two automata are bisimilar, they are also trace equivalent, but the converse is not necessarily true. ## Example: Coffee Machine vs. Insurance Contract Consider two scenarios represented by automata: 1. **Coffee Machine**: - Automaton 1: Decide (tea or coffee) before inserting a coin. - Automaton 2: Insert a coin, then decide (tea or coffee). 2. **Insurance Contract**: - Automaton 1: Decide (cash or monthly payment) before paying. - Automaton 2: Pay, then decide (cash or monthly payment). <figure id="fig:trace_example"> <figcaption>Two automata representing different coffee machines or insurance contracts.</figcaption> </figure> In both cases, the automata representing the two scenarios are **trace equivalent** because they recognize the same language: $L(A_1) = L(A_2) = \{\text{coin.tea}, \text{coin.coffee}\}$. However, they are **not bisimilar**. **Intuition**: - If you are in the initial state of $A_2$ and your friend is in the initial state of $A_1$, your friend can put aThe user wants me to continue the LaTeX document. I stopped mid-sentence while explaining the intuition behind the coffee machine and insurance contract example. I need to complete that sentence and then proceed with the rest of the document, applying the requested formatting with 'tcolorbox'.If you are in the initial state of $A_2$ and your friend is in the initial state of $A_1$, your friend can put a coin and move to the next state. You can also put a coin and move to the next state. - Now, if your friend chooses \"tea\", you cannot simulate it because you are in a state where you must choose \"tea\" or \"coffee\" after putting a coin. - Therefore, there is no bisimulation relation between the initial states of $A_1$ and $A_2$. In the coffee machine scenario, the difference might be negligible. But in the insurance contract scenario, the difference is crucial: deciding upfront vs. deciding later can have vastly different consequences. ## LTL and CTL - **LTL (Linear Temporal Logic)**: LTL formulas are interpreted over traces (sequences of states). LTL **cannot** distinguish between trace equivalent automata. If two automata are trace equivalent, they satisfy the same set of LTL formulas. - **CTL (Computation Tree Logic)**: CTL formulas are interpreted over computation trees. CTL **can** distinguish between bisimilar automata. If two automata are not bisimilar, there might be a CTL formula that is true in one but false in the other. ::: tcolorbox The choice between trace equivalence and bisimulation depends on the specific application and the desired level of granularity in distinguishing between systems. Trace equivalence is a coarser notion, suitable when only the observable sequences of actions matter. Bisimulation is finer-grained, capable of distinguishing systems with different branching behaviors. The complexity of deciding trace equivalence is PSPACE-complete, while the complexity of deciding bisimulation is in P. ::: # Complexity Classes: PSPACE, EXP, and NEXP This section introduces three important complexity classes beyond P and NP:PSPACE, EXP, and NEXP. These classes help us understand the limits of computation in terms of space and time. - **PSPACE**: The class of languages decidable by a deterministic Turing machine using a polynomial amount of space. Formally, $$PSPACE = \bigcup_{k=1}^{\infty} SPACE(n^k)$$ where $SPACE(n^k)$ denotes the set of languages decidable by a deterministic Turing machine using at most $n^k$ space for an input of length $n$. - **EXP (EXPTIME)**: The class of languages decidable by a deterministic Turing machine in exponential time. Formally, $$EXP = \bigcup_{k=1}^{\infty} TIME(2^{n^k})$$ where $TIME(2^{n^k})$ denotes the set of languages decidable by a deterministic Turing machine in at most $2^{n^k}$ time for an input of length $n$. - **NEXP (NEXPTIME)**: The class of languages decidable by a non-deterministic Turing machine in exponential time. Formally, $$NEXP = \bigcup_{k=1}^{\infty} NTIME(2^{n^k})$$ where $NTIME(2^{n^k})$ denotes the set of languages decidable by a non-deterministic Turing machine in at most $2^{n^k}$ time for an input of length $n$. <figure id="fig:complexity_classes"> <figcaption>Relationship between complexity classes</figcaption> </figure> It is known that $P \subseteq NP \subseteq PSPACE \subseteq EXP \subseteq NEXP$, and also that $P \subsetneq EXP$ and $NP \subsetneq NEXP$. However, it is unknown whether $P = NP$, $NP = PSPACE$, $PSPACE = EXP$, or $EXP = NEXP$. :::: tcolorbox ::: theorem **Theorem 4** (If P=NP then EXP=NEXP). *If $P = NP$, then $EXP = NEXP$.* ::: :::: ::: proof *Proof.* **Proof Idea (Padding Technique):** The proof uses a technique called **padding**. The main idea is to take a language $L$ in NEXP and transform it into a related language $L'$ in NP by adding a large number of \"padding\" symbols to the input. If $P = NP$, then $L'$ can be decided in P, and this can be used to decide the original language $L$ in EXP. Let $L \in NEXP$. Then there exists a non-deterministic Turing machine $M$ that decides $L$ in time $2^{n^k}$ for some constant $k$. Define a new language $L'$ (the padded version of $L$) as follows: $$L' = \{ x\#^{2^{|x|^k} - |x|} : x \in L \}$$ where $\#$ is a special symbol not in the alphabet of $L$. The length of the padding is such that the total length of the input string in $L'$ is $2^{|x|^k}$. Since $M$ decides $L$ in time $2^{n^k}$, we can construct a non-deterministic Turing machine $M'$ that decides $L'$ in time linear to its input length. $M'$ on input $y$ first checks if $y$ is of the form $x\#^{2^{|x|^k} - |x|}$. If not, it rejects. Otherwise, it simulates $M$ on $x$ for $|y|$ steps. If $M$ accepts within $|y|$ steps, $M'$ accepts; otherwise, $M'$ rejects. Thus, $L' \in NP$. If $P = NP$, then $L' \in P$. This means there exists a deterministic Turing machine $D$ that decides $L'$ in polynomial time, say $p(n)$. Now we can construct a deterministic Turing machine $D'$ that decides $L$ in exponential time. $D'$ on input $x$ constructs the string $x\#^{2^{|x|^k} - |x|}$ and simulates $D$ on this string. $D'$ accepts if $D$ accepts, and rejects otherwise. The runtime of $D'$ is dominated by the time to construct the padded string, which is $O(2^{|x|^k})$, and the time to simulate $D$, which is $p(2^{|x|^k})$. Thus, $D'$ runs in exponential time, and $L \in EXP$. Since $L$ was an arbitrary language in $NEXP$, we have $NEXP \subseteq EXP$. The other direction, $EXP \subseteq NEXP$ is trivial. Therefore, if $P = NP$, then $EXP = NEXP$. ◻ ::: ## Succinct Problems The concept of **succinctness** introduces a way to represent instances of problems in a more compact form, often leading to higher complexity. Instead of explicitly providing the entire input, a succinct representation provides a smaller, encoded version of the input that can be expanded to obtain the original input. - **Circuit Value Problem (CVP)**: Given a Boolean circuit with no inputs (only constant gates) and a designated output gate, determine the output value of the circuit. CVP is P-complete. - **Circuit Satisfiability Problem (Circuit SAT)**: Given a Boolean circuit with inputs, determine if there exists an assignment to the inputs that makes the output true. Circuit SAT is NP-complete. - **Succinct Circuit Value Problem (Succinct CVP)**: Given a succinct representation of a Boolean circuit (i.e., another circuit that implicitly describes the circuit), determine the output value of the implicitly described circuit. Succinct CVP is EXP-complete. - **Succinct Circuit Satisfiability Problem (Succinct Circuit SAT)**: Given a succinct representation of a Boolean circuit, determine if there exists an assignment to the inputs of the implicitly described circuit that makes the output true. Succinct Circuit SAT is NEXP-complete. :::: tcolorbox ::: definition **Definition 9** (Succinct Representation). *In succinct versions of problems, the input is not given explicitly but is represented implicitly by a smaller, \"meta\" circuit. This meta-circuit, when evaluated, describes the actual input circuit for the problem. More formally, the succinct representation of a circuit $C$ is another circuit $C_{meta}$ such that $C_{meta}(i, j)$ outputs the type of gate $i$ and whether gate $i$ is connected to gate $j$ in the circuit $C$.* ::: :::: For example, in Succinct CVP, instead of being given the entire circuit directly, you are given a smaller circuit that, when evaluated, generates the description of the larger circuit whose value you need to determine. This implicit representation makes the problem exponentially harder. The succinct versions of these problems highlight how the way a problem instance is represented can significantly impact its complexity. They demonstrate that a compact representation can encode an exponentially larger structure, leading to an exponential increase in the computational resources required to solve the problem. # Conclusion This lecture provided a comprehensive overview of the **polynomial hierarchy (PH)**, a fundamental concept in computational complexity theory. We began by defining the PH using both **oracle machines** and **certificates**, establishing the groundwork for understanding its structure and properties. We then introduced **quantified Boolean formulas (QBFs)** as a powerful tool for characterizing the complexity classes within the PH, culminating in the definitions of $\Sigma_i$-SAT and $\Pi_i$-SAT and their respective completeness results. A significant portion of the lecture was dedicated to the intriguing question of whether the polynomial hierarchy **collapses**. We explored the implications of such a collapse and highlighted the prevailing conjecture that the hierarchy is, in fact, strict. We proved that if the hierarchy collapses at any level, it collapses to that level. Furthermore, we delved into the realm of system verification by examining **trace equivalence** and **bisimulation**, two distinct notions of equivalence between automata. The example of coffee machines and insurance contracts illustrated the practical differences between these concepts and why choosing the right notion of equivalence is crucial in different scenarios. We also saw how **Linear Temporal Logic (LTL)** and **Computation Tree Logic (CTL)** relate to trace equivalence and bisimulation, respectively, providing a crucial link between theoretical models and verification techniques. Finally, we expanded our complexity landscape by introducing **PSPACE**, **EXP**, and **NEXP**, showcasing their relationships with the polynomial hierarchy. We discussed the padding technique for proving that if $P=NP$ then $EXP=NEXP$. The concept of **succinctness** was introduced through succinct versions of the circuit value and circuit satisfiability problems, demonstrating how compact representations can lead to increased complexity. ::: tcolorbox - The polynomial hierarchy provides a framework for classifying problems based on their complexity beyond NP and coNP. - QBFs offer a powerful way to define and understand the levels of the polynomial hierarchy. - The collapse of the PH remains a major open problem with significant implications. - Trace equivalence and bisimulation are crucial concepts in system verification, each with its own strengths and weaknesses. Trace equivalence is a coarser notion than bisimulation and is related to LTL, while bisimulation is related to CTL. - Succinct representations can dramatically increase the complexity of problems by encoding an exponentially larger structure in a compact form. ::: **Follow-up Questions:** The following questions represent exciting avenues for further exploration and research: 1. **Equivalence of Definitions:** Can we formally prove the equivalence between the oracle-based and certificate-based definitions of the polynomial hierarchy? This would solidify the foundations of the PH. 2. **Implications of Collapse:** What are the precise implications of the polynomial hierarchy collapsing at a specific level $i$? How would this affect the relationships between other complexity classes and the solvability of certain problems? 3. **LTL vs. CTL:** How can we determine the most appropriate temporal logic (LTL or CTL) for a given system verification task? What are the trade-offs between expressiveness and computational complexity? 4. **Succinctness and Complexity:** How does succinctness affect the complexity of other problems beyond circuit value and satisfiability? Can we develop general techniques for analyzing the complexity of succinctly represented problems? 5. **Beyond PH:** Are there other meaningful hierarchies beyond the polynomial hierarchy that can help us better understand the landscape of computational complexity? These questions highlight the ongoing research and open problems in complexity theory and system verification, underscoring the depth and richness of these fields. They encourage further investigation into the nature of computation and the limits of what can be efficiently computed.