Complexity of Reasoning in AI: Exploring Logic Programming and the Polynomial Hierarchy

Author

Your Name

Published

February 5, 2025

Introduction

This lecture delves into the intricate relationship between reasoning in Artificial Intelligence (AI), specifically within the realm of logic programming, and the established framework of complexity classes. We will investigate four distinct families of logic programs:

Definite Programs: The simplest form, characterized by rules without negation.
General Programs: Programs that incorporate negation as failure in rule bodies.
Disjunctive Programs without Negation: Programs featuring disjunction in rule heads but lacking negation.
General Disjunctive Programs: The most expressive form, combining disjunction in heads and negation in bodies.

The central objective is to analyze the computational complexity associated with determining the existence of stable models for each of these program families. This analysis is paramount for several reasons:

Course Integration: It establishes a connection between this course and other relevant areas, such as formal verification techniques.
Understanding Limitations: It provides a clear understanding of the inherent limitations and capabilities of various AI reasoning methodologies.
Theoretical Foundation: It grounds our discussion in the established theoretical framework presented in the influential paper by Eiter, Gottlob, and their colleagues.

This lecture aims to provide a comprehensive understanding of how different logic programming paradigms map onto the landscape of computational complexity, offering a rigorous basis for further exploration in AI and related fields.

Definite Programs

Definition 1 (Definite Program). A definite program is a set of rules of the form: \[A \leftarrow B_1, \dots, B_n \label{eq:definite_rule}\] where $A, B_1, \dots, B_n$ are atoms, and $n \geq 0$. Crucially, definite programs have the following characteristics:

No Negation: There is no negation (e.g., not) in the rules.
Single Head Atom: Each rule has exactly one atom in the head (left-hand side).

Remark. Remark 1.

Definite programs possess a unique minimum Herbrand model, denoted as $M_P$. This model can be computed using the immediate consequence operator $T_P$, which iteratively applies the rules to derive new facts until a fixed point is reached.

Theorem 1 (Existence of Minimum Herbrand Model).

Every definite program $P$ has a unique minimum Herbrand model, denoted as $M_P$. This model is the smallest model in terms of set inclusion and is fundamental to the semantics of definite programs.

Remark. Remark 2.

It is important to note that if function symbols are permitted, definite programs become Turing complete, meaning they can simulate any computation. However, in the context of this course, we specifically focus on finite domains where function symbols are not used. This restriction allows us to reason about finite portions of the world and ensures that the Herbrand base is finite.

General Programs

Definition 2 (General Program). A general program is a set of rules of the form: \[A \leftarrow B_1, \dots, B_n, \text{not } C_1, \dots, \text{not } C_m \label{eq:general_rule}\] where $A, B_1, \dots, B_n, C_1, \dots, C_m$ are atoms, and $n, m \geq 0$. The key characteristic of general programs is the inclusion of negation as failure (not) in the body of the rules. This allows for non-monotonic reasoning, where the absence of information can be used to infer new conclusions.

Remark. Remark 3.

The introduction of negation as failure in general programs leads to several important differences compared to definite programs:

Non-Intersection Property: The intersection of two models of a general program is not guaranteed to be a model. This contrasts with definite programs, where the intersection of models is always a model.
Non-Monotonicity: The immediate consequence operator $T_P$ is no longer monotonic. This means that adding new information to the program might cause previously derived conclusions to become invalid.

Definition 3 (Stable Model). Let $P$ be a general program and $S$ be a set of atoms. The reduct $P^S$ is a modified version of $P$ obtained through the following steps:

Rule Removal: Remove each rule that has a literal $\text{not } C$ in its body such that $C \in S$. This step eliminates rules where a negated condition is assumed to be false based on the guess $S$.
Negation Removal: Remove all literals of the form $\text{not } C$ from the bodies of the remaining rules. This step simplifies the remaining rules by treating the negated literals as true based on the guess $S$.

A set of atoms $S$ is considered a stable model of $P$ if $S$ is the minimum Herbrand model of the reduct $P^S$.

Remark. Remark 4.

Stable models are minimal Herbrand models, meaning that no proper subset of a stable model is also a model. However, unlike definite programs, general programs can have multiple stable models, and these models are not necessarily the minimum model in the sense of intersection. The concept of a stable model provides a way to select "good" models that are consistent with the program’s rules and assumptions.

Disjunctive Programs without Negation

Definition 4 (Disjunctive Program without Negation). A disjunctive program without negation is a set of rules of the form: \[A_1 \lor \dots \lor A_m \leftarrow B_1, \dots, B_n \label{eq:disjunctive_rule}\] where $A_1, \dots, A_m, B_1, \dots, B_n$ are atoms, $m \geq 0$, and $n \geq 0$. This type of program is characterized by:

Disjunctive Head: The head of each rule can be a disjunction of atoms, allowing for multiple possible consequences.
No Negation: There is no negation (e.g., not) in the rules.

Remark. Remark 5.

If $m = 0$ in the rule definition, the rule becomes a constraint or denial. This type of rule is used to express conditions that must not hold in a model.

Example 1.

Consider the program $P$: \[p \lor q \leftarrow\] The Herbrand models for this program are $\{p\}$, $\{q\}$, and $\{p, q\}$. The stable models are $\{p\}$ and $\{q\}$, as they are the minimal models with respect to set inclusion. The model $\{p,q\}$ is not minimal since $\{p\} \subset \{p,q\}$ and $\{q\} \subset \{p,q\}$.

Definition 5 (Stable Model for Disjunctive Programs without Negation). For disjunctive programs without negation, a stable model is defined as a minimal Herbrand model. This means that a stable model is a model, and no proper subset of it is also a model.

Example 2.

Consider the program $P$: \[\begin{aligned}& \text{man(lazarus)} \leftarrow \\& \text{living}(X) \lor \text{dead}(X) \leftarrow \text{man}(X)\end{aligned}\] The grounding of this program is: \[\begin{aligned}& \text{man(lazarus)} \leftarrow \\& \text{living(lazarus)} \lor \text{dead(lazarus)} \leftarrow \text{man(lazarus)}\end{aligned}\] The stable models for this program are $\{\text{man(lazarus)}, \text{living(lazarus)}\}$ and $\{\text{man(lazarus)}, \text{dead(lazarus)}\}$. These are minimal models because neither of them is a subset of the other, and both satisfy the program’s rules.

Example 3.

Consider the program $P$: \[\begin{aligned}& a \lor b \leftarrow \\& b \lor c \leftarrow a\end{aligned}\] The stable models for this program are $\{a, c\}$ and $\{b\}$. To see this, consider the possible models:

$\{a\}$: This is not a model because the second rule requires either $b$ or $c$ to be true if $a$ is true.
$\{b\}$: This is a model. The first rule is satisfied, and the second rule is not active.
$\{c\}$: This is not a model because the first rule requires either $a$ or $b$ to be true.
$\{a,b\}$: This is a model, but it is not minimal because $\{b\}$ is a smaller model.
$\{a,c\}$: This is a model. The first rule is satisfied because $a$ is true, and the second rule is satisfied because $a$ is true and $c$ is true.
$\{b,c\}$: This is not a model because the first rule requires either $a$ or $b$ to be true, and $a$ is not present.
$\{a,b,c\}$: This is a model, but it is not minimal because $\{a,c\}$ and $\{b\}$ are smaller models.

Example 4 (Three-Coloring).

Consider a graph with nodes $\{a, b, c\}$ and edges $\{(a, b), (a, c)\}$. We have three colors: red, green, and blue. The three-coloring problem can be encoded as: \[\begin{aligned}& \text{color}(X, \text{red}) \lor \text{color}(X, \text{green}) \lor \text{color}(X, \text{blue}) \leftarrow \text{node}(X) \\& \leftarrow \text{edge}(X, Y), \text{color}(X, C), \text{color}(Y, C)\end{aligned}\] This program encodes an NP-complete problem. The first rule ensures that each node is assigned at least one color. The second rule is a constraint that prevents adjacent nodes from having the same color.

General Disjunctive Programs

Definition 6 (General Disjunctive Program). A general disjunctive program is a set of rules of the form: \[A_1 \lor \dots \lor A_m \leftarrow B_1, \dots, B_n, \text{not } C_1, \dots, \text{not } C_k \label{eq:general_disjunctive_rule}\] where $A_1, \dots, A_m, B_1, \dots, B_n, C_1, \dots, C_k$ are atoms, and $m, n, k \geq 0$. This type of program combines the features of general programs and disjunctive programs, allowing for:

Disjunctive Head: The head of each rule can be a disjunction of atoms.
Negation as Failure: Negation as failure (not) is allowed in the body of the rules.

Definition 7 (Stable Model for General Disjunctive Programs). Let $P$ be a general disjunctive program and $S$ be a set of atoms. The reduct $P^S$ is obtained from $P$ using the following steps:

Rule Removal: Remove each rule that has a literal $\text{not } C$ in its body such that $C \in S$.
Negation Removal: Remove all literals of the form $\text{not } C$ from the bodies of the remaining rules.

A set of atoms $S$ is a stable model of $P$ if $S$ is a minimal model of the reduct $P^S$.

Example 5 (Strategic Companies).

Consider a scenario with a set of companies $C$ and a set of goods $G$. Each company produces a subset of the goods. A company $C_i$ can be controlled by a set of companies $O_i$. A set $S \subseteq C$ is defined as a strategic set if it satisfies the following conditions:

Production Coverage: All goods in $G$ are produced by at least one company in $S$.
Control Inclusion: If the set of controlling companies $O_i$ for a company $C_i$ is a subset of $S$ (i.e., $O_i \subseteq S$), then $C_i$ must also be in $S$.
Minimality: $S$ is minimal with respect to the above properties, meaning no proper subset of $S$ satisfies both conditions.

This problem is $\Sigma_2^P$-complete, indicating its high computational complexity.

Example 6 (Simplified Strategic Companies).

To simplify the strategic companies problem, we can assume that each product is produced by at most four companies and each company is controlled by at most four companies. This can be represented by facts like: \[\begin{aligned}& \text{produced\_by}(P, C_1, C_2, C_3, C_4) \\& \text{controlled\_by}(C, C_1, C_2, C_3, C_4)\end{aligned}\] We can also add pairs of companies that must be in the strategic set using facts like strategic_pair(C1, C2). The problem can be encoded using the following rules: \[\begin{aligned}& \text{strategic}(X_1) \lor \text{strategic}(X_2) \lor \text{strategic}(X_3) \lor \text{strategic}(X_4) \leftarrow \text{produced\_by}(G, X_1, X_2, X_3, X_4) \\& \text{strategic}(W) \leftarrow \text{strategic}(X_1), \text{strategic}(X_2), \text{strategic}(X_3), \text{strategic}(X_4), \\& \hspace{8em} \text{controlled\_by}(W, X_1, X_2, X_3, X_4) \\& \leftarrow \text{strategic\_pair}(X, Y), \text{not strategic}(X) \\& \leftarrow \text{strategic\_pair}(X, Y), \text{not strategic}(Y)\end{aligned}\] The first rule ensures that at least one company producing a good is in the strategic set. The second rule ensures that if all controlling companies are in the strategic set, then the controlled company is also in the strategic set. The last two rules are constraints that enforce the inclusion of specified pairs of companies in the strategic set.

Complexity Analysis

Consistency Problem

The consistency problem is the problem of determining whether a given logic program has at least one stable model. This is a fundamental question in the study of logic programming, as the existence of a stable model is a prerequisite for meaningful reasoning.

Definite Programs

Theorem 2 (Consistency of Definite Programs).

For a definite program $P$, the consistency problem is trivial. A stable model always exists, and it is the unique minimum Herbrand model $M_P$.

Proof. Proof.

The minimum Herbrand model $M_P$ can be computed in polynomial time using the immediate consequence operator $T_P$. Since a minimum model always exists for definite programs, the answer to the consistency problem is always "yes". The computation starts with the facts in the program and iteratively applies the rules until a fixed point is reached. This fixed point is the minimum Herbrand model.

◻

General Programs

Theorem 3 (Consistency of General Programs).

Establishing whether a general ground program admits a stable model is NP-complete.

Proof. Proof.

NP Membership: To show that the problem is in NP, we need to demonstrate that a candidate solution (a stable model) can be verified in polynomial time. A guess $S$ for a stable model can be verified as follows:

Compute the Reduct: Compute the reduct $P^S$, which takes linear time with respect to the size of the program.
Compute the Minimum Model: Compute the minimum Herbrand model of $P^S$ using the $T_P$ operator. This step takes polynomial time.
Check for Equality: Check if the computed minimum model is equal to the initial guess $S$.

Since all these steps can be performed in polynomial time, the problem is in NP.

NP Completeness: To prove NP-completeness, we reduce the 3SAT problem to the consistency problem for general programs. For each variable $A$ in the 3SAT instance, introduce the following rules: \[\begin{aligned}& A \leftarrow \text{not } \neg A \\& \neg A \leftarrow \text{not } A\end{aligned}\] These rules enforce a choice between $A$ and $\neg A$ in any stable model. For each clause $C_i = (l_1 \lor l_2 \lor l_3)$, introduce rules: \[\begin{aligned}& C_i \leftarrow l_1 \\& C_i \leftarrow l_2 \\& C_i \leftarrow l_3\end{aligned}\] These rules ensure that if at least one literal in the clause is true, then $C_i$ is true. Finally, add the following constraint: \[\leftarrow \text{not } C_i\] for each clause $C_i$. This constraint ensures that all clauses are satisfied in any stable model. This reduction can be done in polynomial time, and a stable model exists if and only if the 3SAT instance is satisfiable.

◻

Disjunctive Programs without Negation

Theorem 4 (Consistency of Disjunctive Programs without Negation).

Establishing whether a disjunctive program without negation admits a stable model is NP-complete.

Proof. Proof.

NP Membership: To show that the problem is in NP, we need to demonstrate that a candidate solution (a stable model) can be verified in polynomial time. A guess $S$ can be verified as follows:

Check if it is a Model: Verify if $S$ is a model by scanning the program and checking each rule. This step takes polynomial time.
Existence of Minimal Model: If $S$ is a model, then a minimal model exists (either $S$ itself or a subset of $S$). We don’t need to find the minimal model, just verify that a model exists, and if a model exists, a minimal model exists.

Since these steps can be performed in polynomial time, the problem is in NP.

NP Completeness: To prove NP-completeness, we reduce the 3SAT problem to the consistency problem for disjunctive programs without negation. For each clause $(l_1 \lor l_2 \lor l_3)$ in the 3SAT instance, introduce the following rule: \[l_1 \lor l_2 \lor l_3 \leftarrow\] This rule directly encodes the clause as a disjunction. This reduction is straightforward and can be done in polynomial time. A minimal model exists if and only if the 3SAT instance is satisfiable.

◻

General Disjunctive Programs

Definition 8 (Polynomial Hierarchy). The polynomial hierarchy is a hierarchy of complexity classes that extends beyond NP. It is defined as follows:

$\Sigma_0^P = \Pi_0^P = P$
$\Sigma_{k+1}^P = NP^{\Sigma_k^P}$
$\Pi_{k+1}^P = coNP^{\Sigma_k^P}$

where $NP^A$ denotes the class of languages decidable by a non-deterministic Turing machine in polynomial time with access to an oracle for a language $A$.

Remark. Remark 6.

$\Sigma_1^P = NP$, and $\Sigma_2^P = NP^{NP}$. The typical problem for $\Sigma_2^P$ is to determine the validity of formulas of the form: \[\exists X_1 \dots \exists X_n \forall Y_1 \dots \forall Y_m \phi(X_1, \dots, X_n, Y_1, \dots, Y_m)\] where $\phi$ is a propositional formula.

Theorem 5 (Consistency of General Disjunctive Programs).

Establishing whether a general disjunctive program admits a stable model is $\Sigma_2^P$-complete.

Proof. Proof.

$\Sigma_2^P$ Membership: To show that the problem is in $\Sigma_2^P$, we need to demonstrate that a candidate solution (a stable model) can be verified in polynomial time with access to an NP oracle. A guess $S$ can be verified as follows:

Compute the Reduct: Compute the reduct $P^S$, which takes linear time.
Check if it is a Model: Check if $S$ is a model of $P^S$, which takes polynomial time.
Check for Minimality: To check if $S$ is minimal, ask the NP oracle if there exists a subset $S' \subset S$ that is a model of $P^S$. If the oracle answers "no", then $S$ is a minimal model.

Since these steps can be performed in polynomial time with one call to an NP oracle, the problem is in $\Sigma_2^P$.

$\Sigma_2^P$ Completeness: To prove $\Sigma_2^P$-completeness, we reduce the problem of deciding the validity of a $\exists \forall$ formula to the consistency problem for general disjunctive programs. Consider a formula of the form: \[\exists X_1, \dots, X_n \forall Y_1, \dots, Y_m \phi(X_1, \dots, X_n, Y_1, \dots, Y_m)\] where $\phi$ is in disjunctive normal form. For each $X_i$ and $Y_i$, introduce variables $X_i, X_i', Y_i, Y_i'$. Introduce the following rules: \[\begin{aligned}& X_i \lor X_i' \leftarrow \\& Y_i \lor Y_i' \leftarrow\end{aligned}\] These rules enforce a choice between $X_i$ and $X_i'$, and $Y_i$ and $Y_i'$. Let $\phi = D_1 \lor \dots \lor D_k$, where each $D_i$ is a conjunction of literals. For each $D_i$, introduce a rule: \[W \leftarrow D_i\] where $D_i$ is the conjunction of the corresponding literals, using $X_i'$ for $\neg X_i$ and $Y_i'$ for $\neg Y_i$. Add the rules: \[\begin{aligned}& Y_i \leftarrow W \\& Y_i' \leftarrow W\end{aligned}\] Finally, add the rule: \[W \leftarrow \text{not } W\] This reduction can be done in polynomial time. The formula is valid if and only if the constructed program has a stable model. The proof involves showing that if $S$ is a stable model, then $W$ must be true. This forces one of the $D_i$ to be true for all possible assignments of $Y_i$, which implies the validity of the formula. Conversely, if the formula is valid, a stable model can be constructed.

◻

Conclusion

This lecture has provided a comprehensive exploration of the complexity of reasoning in AI, specifically through the lens of logic programming. We have examined four distinct families of logic programs:

Definite Programs: The simplest form, characterized by rules without negation.
General Programs: Programs that incorporate negation as failure in rule bodies.
Disjunctive Programs without Negation: Programs featuring disjunction in rule heads but lacking negation.
General Disjunctive Programs: The most expressive form, combining disjunction in heads and negation in bodies.

We have analyzed the complexity of the consistency problem—determining whether a given program has a stable model—for each family, demonstrating a clear progression in computational difficulty:

Definite Programs: The consistency problem is trivial, as a stable model always exists and can be found in polynomial time.
General Programs: The consistency problem is NP-complete, indicating that finding a stable model is computationally hard.
Disjunctive Programs without Negation: The consistency problem is also NP-complete, highlighting that disjunction alone introduces significant complexity.
General Disjunctive Programs: The consistency problem is $\Sigma_2^P$-complete, placing it higher in the polynomial hierarchy and making it even more computationally challenging.

The analysis underscores the increasing complexity as we move from simpler to more expressive logic programming frameworks. This understanding is crucial for several reasons:

System Design: It provides insights into the computational limitations and capabilities of different reasoning approaches, which is essential for designing and implementing efficient AI systems.
Trade-offs: It establishes a formal framework for understanding the trade-offs between expressiveness and computational cost in logic programming.
Practical Implications: It highlights the practical implications of theoretical complexity results for the performance of logic programming solvers.

Key Takeaways:

Definite programs have a unique minimum Herbrand model, making the consistency problem trivial.
General programs introduce negation as failure, leading to NP-completeness for the consistency problem.
Disjunctive programs without negation also exhibit NP-completeness, even without negation.
General disjunctive programs, which combine disjunction and negation, result in $\Sigma_2^P$-completeness, placing them higher in the polynomial hierarchy.
The complexity analysis provides a formal frameworkfor understanding the trade-offs between expressiveness and computational cost in logic programming.

Follow-up Questions:

How does the complexity of the consistency problem relate to the practical performance of logic programming solvers like Clingo and DLV?
Can you think of real-world problems that are naturally modeled using general disjunctive programs, and how might their $\Sigma_2^P$-completeness impact their solvability?
What are the implications of the polynomial hierarchy for the development of AI systems, particularly in areas like planning and verification?
Explore the concept of the arithmetical hierarchy and its relationship to the polynomial hierarchy. How do these hierarchies inform our understanding of computability and complexity?

For the next lecture, please bring your laptops as we will be engaging in hands-on ASP programming exercises. This will provide an opportunity to apply the theoretical concepts discussed today and gain practical experience with logic programming using Answer Set Programming (ASP).

--- title: "Complexity of Reasoning in AI: Exploring Logic Programming and the Polynomial Hierarchy" author: "Your Name" date: "2025-02-05" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction ::: tcolorbox This lecture delves into the intricate relationship between reasoning in Artificial Intelligence (AI), specifically within the realm of logic programming, and the established framework of complexity classes. We will investigate four distinct families of logic programs: 1. **Definite Programs**: The simplest form, characterized by rules without negation. 2. **General Programs**: Programs that incorporate negation as failure in rule bodies. 3. **Disjunctive Programs without Negation**: Programs featuring disjunction in rule heads but lacking negation. 4. **General Disjunctive Programs**: The most expressive form, combining disjunction in heads and negation in bodies. ::: The central objective is to analyze the computational complexity associated with determining the existence of stable models for each of these program families. This analysis is paramount for several reasons: - **Course Integration**: It establishes a connection between this course and other relevant areas, such as formal verification techniques. - **Understanding Limitations**: It provides a clear understanding of the inherent limitations and capabilities of various AI reasoning methodologies. - **Theoretical Foundation**: It grounds our discussion in the established theoretical framework presented in the influential paper by Eiter, Gottlob, and their colleagues. This lecture aims to provide a comprehensive understanding of how different logic programming paradigms map onto the landscape of computational complexity, offering a rigorous basis for further exploration in AI and related fields. # Definite Programs :::: tcolorbox ::: definition **Definition 1** (Definite Program). A *definite program* is a set of rules of the form: $$A \leftarrow B_1, \dots, B_n \label{eq:definite_rule}$$ where $A, B_1, \dots, B_n$ are atoms, and $n \geq 0$. Crucially, definite programs have the following characteristics: - **No Negation**: There is no negation (e.g., `not`) in the rules. - **Single Head Atom**: Each rule has exactly one atom in the head (left-hand side). ::: :::: :::: remark **Remark 1**. ::: tcolorbox Definite programs possess a unique minimum Herbrand model, denoted as $M_P$. This model can be computed using the immediate consequence operator $T_P$, which iteratively applies the rules to derive new facts until a fixed point is reached. ::: :::: :::: theorem **Theorem 1** (Existence of Minimum Herbrand Model). ::: tcolorbox *Every definite program $P$ has a unique minimum Herbrand model, denoted as $M_P$. This model is the smallest model in terms of set inclusion and is fundamental to the semantics of definite programs.* ::: :::: :::: remark **Remark 2**. ::: tcolorbox It is important to note that if function symbols are permitted, definite programs become Turing complete, meaning they can simulate any computation. However, in the context of this course, we specifically focus on finite domains where function symbols are not used. This restriction allows us to reason about finite portions of the world and ensures that the Herbrand base is finite. ::: :::: # General Programs :::: tcolorbox ::: definition **Definition 2** (General Program). A *general program* is a set of rules of the form: $$A \leftarrow B_1, \dots, B_n, \text{not } C_1, \dots, \text{not } C_m \label{eq:general_rule}$$ where $A, B_1, \dots, B_n, C_1, \dots, C_m$ are atoms, and $n, m \geq 0$. The key characteristic of general programs is the inclusion of *negation as failure* (`not`) in the body of the rules. This allows for non-monotonic reasoning, where the absence of information can be used to infer new conclusions. ::: :::: :::: remark **Remark 3**. ::: tcolorbox The introduction of negation as failure in general programs leads to several important differences compared to definite programs: - **Non-Intersection Property**: The intersection of two models of a general program is not guaranteed to be a model. This contrasts with definite programs, where the intersection of models is always a model. - **Non-Monotonicity**: The immediate consequence operator $T_P$ is no longer monotonic. This means that adding new information to the program might cause previously derived conclusions to become invalid. ::: :::: :::: tcolorbox ::: definition **Definition 3** (Stable Model). Let $P$ be a general program and $S$ be a set of atoms. The *reduct* $P^S$ is a modified version of $P$ obtained through the following steps: 1. **Rule Removal**: Remove each rule that has a literal $\text{not } C$ in its body such that $C \in S$. This step eliminates rules where a negated condition is assumed to be false based on the guess $S$. 2. **Negation Removal**: Remove all literals of the form $\text{not } C$ from the bodies of the remaining rules. This step simplifies the remaining rules by treating the negated literals as true based on the guess $S$. A set of atoms $S$ is considered a *stable model* of $P$ if $S$ is the minimum Herbrand model of the reduct $P^S$. ::: :::: :::: remark **Remark 4**. ::: tcolorbox Stable models are minimal Herbrand models, meaning that no proper subset of a stable model is also a model. However, unlike definite programs, general programs can have multiple stable models, and these models are not necessarily the minimum model in the sense of intersection. The concept of a stable model provides a way to select \"good\" models that are consistent with the program's rules and assumptions. ::: :::: # Disjunctive Programs without Negation :::: tcolorbox ::: definition **Definition 4** (Disjunctive Program without Negation). A *disjunctive program without negation* is a set of rules of the form: $$A_1 \lor \dots \lor A_m \leftarrow B_1, \dots, B_n \label{eq:disjunctive_rule}$$ where $A_1, \dots, A_m, B_1, \dots, B_n$ are atoms, $m \geq 0$, and $n \geq 0$. This type of program is characterized by: - **Disjunctive Head**: The head of each rule can be a disjunction of atoms, allowing for multiple possible consequences. - **No Negation**: There is no negation (e.g., `not`) in the rules. ::: :::: :::: remark **Remark 5**. ::: tcolorbox If $m = 0$ in the rule definition, the rule becomes a *constraint* or *denial*. This type of rule is used to express conditions that must not hold in a model. ::: :::: :::: example **Example 1**. ::: tcolorbox Consider the program $P$: $$p \lor q \leftarrow$$ The Herbrand models for this program are $\{p\}$, $\{q\}$, and $\{p, q\}$. The stable models are $\{p\}$ and $\{q\}$, as they are the minimal models with respect to set inclusion. The model $\{p,q\}$ is not minimal since $\{p\} \subset \{p,q\}$ and $\{q\} \subset \{p,q\}$. ::: :::: :::: tcolorbox ::: definition **Definition 5** (Stable Model for Disjunctive Programs without Negation). For disjunctive programs without negation, a stable model is defined as a minimal Herbrand model. This means that a stable model is a model, and no proper subset of it is also a model. ::: :::: :::: example **Example 2**. ::: tcolorbox Consider the program $P$: $$\begin{aligned}& \text{man(lazarus)} \leftarrow \\& \text{living}(X) \lor \text{dead}(X) \leftarrow \text{man}(X)\end{aligned}$$ The grounding of this program is: $$\begin{aligned}& \text{man(lazarus)} \leftarrow \\& \text{living(lazarus)} \lor \text{dead(lazarus)} \leftarrow \text{man(lazarus)}\end{aligned}$$ The stable models for this program are $\{\text{man(lazarus)}, \text{living(lazarus)}\}$ and $\{\text{man(lazarus)}, \text{dead(lazarus)}\}$. These are minimal models because neither of them is a subset of the other, and both satisfy the program's rules. ::: :::: :::: example **Example 3**. ::: tcolorbox Consider the program $P$: $$\begin{aligned}& a \lor b \leftarrow \\& b \lor c \leftarrow a\end{aligned}$$ The stable models for this program are $\{a, c\}$ and $\{b\}$. To see this, consider the possible models: - $\{a\}$: This is not a model because the second rule requires either $b$ or $c$ to be true if $a$ is true. - $\{b\}$: This is a model. The first rule is satisfied, and the second rule is not active. - $\{c\}$: This is not a model because the first rule requires either $a$ or $b$ to be true. - $\{a,b\}$: This is a model, but it is not minimal because $\{b\}$ is a smaller model. - $\{a,c\}$: This is a model. The first rule is satisfied because $a$ is true, and the second rule is satisfied because $a$ is true and $c$ is true. - $\{b,c\}$: This is not a model because the first rule requires either $a$ or $b$ to be true, and $a$ is not present. - $\{a,b,c\}$: This is a model, but it is not minimal because $\{a,c\}$ and $\{b\}$ are smaller models. ::: :::: :::: example **Example 4** (Three-Coloring). ::: tcolorbox Consider a graph with nodes $\{a, b, c\}$ and edges $\{(a, b), (a, c)\}$. We have three colors: red, green, and blue. The three-coloring problem can be encoded as: $$\begin{aligned}& \text{color}(X, \text{red}) \lor \text{color}(X, \text{green}) \lor \text{color}(X, \text{blue}) \leftarrow \text{node}(X) \\& \leftarrow \text{edge}(X, Y), \text{color}(X, C), \text{color}(Y, C)\end{aligned}$$ This program encodes an NP-complete problem. The first rule ensures that each node is assigned at least one color. The second rule is a constraint that prevents adjacent nodes from having the same color. ::: :::: # General Disjunctive Programs :::: tcolorbox ::: definition **Definition 6** (General Disjunctive Program). A *general disjunctive program* is a set of rules of the form: $$A_1 \lor \dots \lor A_m \leftarrow B_1, \dots, B_n, \text{not } C_1, \dots, \text{not } C_k \label{eq:general_disjunctive_rule}$$ where $A_1, \dots, A_m, B_1, \dots, B_n, C_1, \dots, C_k$ are atoms, and $m, n, k \geq 0$. This type of program combines the features of general programs and disjunctive programs, allowing for: - **Disjunctive Head**: The head of each rule can be a disjunction of atoms. - **Negation as Failure**: Negation as failure (`not`) is allowed in the body of the rules. ::: :::: :::: tcolorbox ::: definition **Definition 7** (Stable Model for General Disjunctive Programs). Let $P$ be a general disjunctive program and $S$ be a set of atoms. The *reduct* $P^S$ is obtained from $P$ using the following steps: 1. **Rule Removal**: Remove each rule that has a literal $\text{not } C$ in its body such that $C \in S$. 2. **Negation Removal**: Remove all literals of the form $\text{not } C$ from the bodies of the remaining rules. A set of atoms $S$ is a *stable model* of $P$ if $S$ is a minimal model of the reduct $P^S$. ::: :::: :::: example **Example 5** (Strategic Companies). ::: tcolorbox Consider a scenario with a set of companies $C$ and a set of goods $G$. Each company produces a subset of the goods. A company $C_i$ can be controlled by a set of companies $O_i$. A set $S \subseteq C$ is defined as a *strategic set* if it satisfies the following conditions: 1. **Production Coverage**: All goods in $G$ are produced by at least one company in $S$. 2. **Control Inclusion**: If the set of controlling companies $O_i$ for a company $C_i$ is a subset of $S$ (i.e., $O_i \subseteq S$), then $C_i$ must also be in $S$. 3. **Minimality**: $S$ is minimal with respect to the above properties, meaning no proper subset of $S$ satisfies both conditions. This problem is $\Sigma_2^P$-complete, indicating its high computational complexity. ::: :::: :::: example **Example 6** (Simplified Strategic Companies). ::: tcolorbox To simplify the strategic companies problem, we can assume that each product is produced by at most four companies and each company is controlled by at most four companies. This can be represented by facts like: $$\begin{aligned}& \text{produced\_by}(P, C_1, C_2, C_3, C_4) \\& \text{controlled\_by}(C, C_1, C_2, C_3, C_4)\end{aligned}$$ We can also add pairs of companies that must be in the strategic set using facts like `strategic_pair(C1, C2)`. The problem can be encoded using the following rules: $$\begin{aligned}& \text{strategic}(X_1) \lor \text{strategic}(X_2) \lor \text{strategic}(X_3) \lor \text{strategic}(X_4) \leftarrow \text{produced\_by}(G, X_1, X_2, X_3, X_4) \\& \text{strategic}(W) \leftarrow \text{strategic}(X_1), \text{strategic}(X_2), \text{strategic}(X_3), \text{strategic}(X_4), \\& \hspace{8em} \text{controlled\_by}(W, X_1, X_2, X_3, X_4) \\& \leftarrow \text{strategic\_pair}(X, Y), \text{not strategic}(X) \\& \leftarrow \text{strategic\_pair}(X, Y), \text{not strategic}(Y)\end{aligned}$$ The first rule ensures that at least one company producing a good is in the strategic set. The second rule ensures that if all controlling companies are in the strategic set, then the controlled company is also in the strategic set. The last two rules are constraints that enforce the inclusion of specified pairs of companies in the strategic set. ::: :::: # Complexity Analysis ## Consistency Problem ::: tcolorbox The *consistency problem* is the problem of determining whether a given logic program has at least one stable model. This is a fundamental question in the study of logic programming, as the existence of a stable model is a prerequisite for meaningful reasoning. ::: ## Definite Programs :::: theorem **Theorem 2** (Consistency of Definite Programs). ::: tcolorbox *For a definite program $P$, the consistency problem is trivial. A stable model always exists, and it is the unique minimum Herbrand model $M_P$.* ::: :::: :::: proof *Proof.* ::: tcolorbox The minimum Herbrand model $M_P$ can be computed in polynomial time using the immediate consequence operator $T_P$. Since a minimum model always exists for definite programs, the answer to the consistency problem is always \"yes\". The computation starts with the facts in the program and iteratively applies the rules until a fixed point is reached. This fixed point is the minimum Herbrand model. ::: ◻ :::: ## General Programs :::: theorem **Theorem 3** (Consistency of General Programs). ::: tcolorbox *Establishing whether a general ground program admits a stable model is NP-complete.* ::: :::: ::::: proof *Proof.* ::: tcolorbox **NP Membership:** To show that the problem is in NP, we need to demonstrate that a candidate solution (a stable model) can be verified in polynomial time. A guess $S$ for a stable model can be verified as follows: 1. **Compute the Reduct**: Compute the reduct $P^S$, which takes linear time with respect to the size of the program. 2. **Compute the Minimum Model**: Compute the minimum Herbrand model of $P^S$ using the $T_P$ operator. This step takes polynomial time. 3. **Check for Equality**: Check if the computed minimum model is equal to the initial guess $S$. Since all these steps can be performed in polynomial time, the problem is in NP. ::: ::: tcolorbox **NP Completeness:** To prove NP-completeness, we reduce the 3SAT problem to the consistency problem for general programs. For each variable $A$ in the 3SAT instance, introduce the following rules: $$\begin{aligned}& A \leftarrow \text{not } \neg A \\& \neg A \leftarrow \text{not } A\end{aligned}$$ These rules enforce a choice between $A$ and $\neg A$ in any stable model. For each clause $C_i = (l_1 \lor l_2 \lor l_3)$, introduce rules: $$\begin{aligned}& C_i \leftarrow l_1 \\& C_i \leftarrow l_2 \\& C_i \leftarrow l_3\end{aligned}$$ These rules ensure that if at least one literal in the clause is true, then $C_i$ is true. Finally, add the following constraint: $$\leftarrow \text{not } C_i$$ for each clause $C_i$. This constraint ensures that all clauses are satisfied in any stable model. This reduction can be done in polynomial time, and a stable model exists if and only if the 3SAT instance is satisfiable. ::: ◻ ::::: ## Disjunctive Programs without Negation :::: theorem **Theorem 4** (Consistency of Disjunctive Programs without Negation). ::: tcolorbox *Establishing whether a disjunctive program without negation admits a stable model is NP-complete.* ::: :::: ::::: proof *Proof.* ::: tcolorbox **NP Membership:** To show that the problem is in NP, we need to demonstrate that a candidate solution (a stable model) can be verified in polynomial time. A guess $S$ can be verified as follows: 1. **Check if it is a Model**: Verify if $S$ is a model by scanning the program and checking each rule. This step takes polynomial time. 2. **Existence of Minimal Model**: If $S$ is a model, then a minimal model exists (either $S$ itself or a subset of $S$). We don't need to find the minimal model, just verify that a model exists, and if a model exists, a minimal model exists. Since these steps can be performed in polynomial time, the problem is in NP. ::: ::: tcolorbox **NP Completeness:** To prove NP-completeness, we reduce the 3SAT problem to the consistency problem for disjunctive programs without negation. For each clause $(l_1 \lor l_2 \lor l_3)$ in the 3SAT instance, introduce the following rule: $$l_1 \lor l_2 \lor l_3 \leftarrow$$ This rule directly encodes the clause as a disjunction. This reduction is straightforward and can be done in polynomial time. A minimal model exists if and only if the 3SAT instance is satisfiable. ::: ◻ ::::: ## General Disjunctive Programs :::: tcolorbox ::: definition **Definition 8** (Polynomial Hierarchy). The polynomial hierarchy is a hierarchy of complexity classes that extends beyond NP. It is defined as follows: - $\Sigma_0^P = \Pi_0^P = P$ - $\Sigma_{k+1}^P = NP^{\Sigma_k^P}$ - $\Pi_{k+1}^P = coNP^{\Sigma_k^P}$ where $NP^A$ denotes the class of languages decidable by a non-deterministic Turing machine in polynomial time with access to an oracle for a language $A$. ::: :::: :::: remark **Remark 6**. ::: tcolorbox $\Sigma_1^P = NP$, and $\Sigma_2^P = NP^{NP}$. The typical problem for $\Sigma_2^P$ is to determine the validity of formulas of the form: $$\exists X_1 \dots \exists X_n \forall Y_1 \dots \forall Y_m \phi(X_1, \dots, X_n, Y_1, \dots, Y_m)$$ where $\phi$ is a propositional formula. ::: :::: :::: theorem **Theorem 5** (Consistency of General Disjunctive Programs). ::: tcolorbox *Establishing whether a general disjunctive program admits a stable model is $\Sigma_2^P$-complete.* ::: :::: ::::: proof *Proof.* ::: tcolorbox **$\Sigma_2^P$ Membership:** To show that the problem is in $\Sigma_2^P$, we need to demonstrate that a candidate solution (a stable model) can be verified in polynomial time with access to an NP oracle. A guess $S$ can be verified as follows: 1. **Compute the Reduct**: Compute the reduct $P^S$, which takes linear time. 2. **Check if it is a Model**: Check if $S$ is a model of $P^S$, which takes polynomial time. 3. **Check for Minimality**: To check if $S$ is minimal, ask the NP oracle if there exists a subset $S' \subset S$ that is a model of $P^S$. If the oracle answers \"no\", then $S$ is a minimal model. Since these steps can be performed in polynomial time with one call to an NP oracle, the problem is in $\Sigma_2^P$. ::: ::: tcolorbox **$\Sigma_2^P$ Completeness:** To prove $\Sigma_2^P$-completeness, we reduce the problem of deciding the validity of a $\exists \forall$ formula to the consistency problem for general disjunctive programs. Consider a formula of the form: $$\exists X_1, \dots, X_n \forall Y_1, \dots, Y_m \phi(X_1, \dots, X_n, Y_1, \dots, Y_m)$$ where $\phi$ is in disjunctive normal form. For each $X_i$ and $Y_i$, introduce variables $X_i, X_i', Y_i, Y_i'$. Introduce the following rules: $$\begin{aligned}& X_i \lor X_i' \leftarrow \\& Y_i \lor Y_i' \leftarrow\end{aligned}$$ These rules enforce a choice between $X_i$ and $X_i'$, and $Y_i$ and $Y_i'$. Let $\phi = D_1 \lor \dots \lor D_k$, where each $D_i$ is a conjunction of literals. For each $D_i$, introduce a rule: $$W \leftarrow D_i$$ where $D_i$ is the conjunction of the corresponding literals, using $X_i'$ for $\neg X_i$ and $Y_i'$ for $\neg Y_i$. Add the rules: $$\begin{aligned}& Y_i \leftarrow W \\& Y_i' \leftarrow W\end{aligned}$$ Finally, add the rule: $$W \leftarrow \text{not } W$$ This reduction can be done in polynomial time. The formula is valid if and only if the constructed program has a stable model. The proof involves showing that if $S$ is a stable model, then $W$ must be true. This forces one of the $D_i$ to be true for all possible assignments of $Y_i$, which implies the validity of the formula. Conversely, if the formula is valid, a stable model can be constructed. ::: ◻ ::::: # Conclusion ::: tcolorbox This lecture has provided a comprehensive exploration of the complexity of reasoning in AI, specifically through the lens of logic programming. We have examined four distinct families of logic programs: 1. **Definite Programs**: The simplest form, characterized by rules without negation. 2. **General Programs**: Programs that incorporate negation as failure in rule bodies. 3. **Disjunctive Programs without Negation**: Programs featuring disjunction in rule heads but lacking negation. 4. **General Disjunctive Programs**: The most expressive form, combining disjunction in heads and negation in bodies. ::: We have analyzed the complexity of the consistency problem---determining whether a given program has a stable model---for each family, demonstrating a clear progression in computational difficulty: - **Definite Programs**: The consistency problem is **trivial**, as a stable model always exists and can be found in polynomial time. - **General Programs**: The consistency problem is **NP-complete**, indicating that finding a stable model is computationally hard. - **Disjunctive Programs without Negation**: The consistency problem is also **NP-complete**, highlighting that disjunction alone introduces significant complexity. - **General Disjunctive Programs**: The consistency problem is **$\Sigma_2^P$-complete**, placing it higher in the polynomial hierarchy and making it even more computationally challenging. ::: tcolorbox The analysis underscores the increasing complexity as we move from simpler to more expressive logic programming frameworks. This understanding is crucial for several reasons: - **System Design**: It provides insights into the computational limitations and capabilities of different reasoning approaches, which is essential for designing and implementing efficient AI systems. - **Trade-offs**: It establishes a formal framework for understanding the trade-offs between expressiveness and computational cost in logic programming. - **Practical Implications**: It highlights the practical implications of theoretical complexity results for the performance of logic programming solvers. ::: **Key Takeaways:** - Definite programs have a unique minimum Herbrand model, making the consistency problem trivial. - General programs introduce negation as failure, leading to NP-completeness for the consistency problem. - Disjunctive programs without negation also exhibit NP-completeness, even without negation. - General disjunctive programs, which combine disjunction and negation, result in $\Sigma_2^P$-completeness, placing them higher in the polynomial hierarchy. - The complexity analysis provides a formal frameworkfor understanding the trade-offs between expressiveness and computational cost in logic programming. **Follow-up Questions:** 1. How does the complexity of the consistency problem relate to the practical performance of logic programming solvers like Clingo and DLV? 2. Can you think of real-world problems that are naturally modeled using general disjunctive programs, and how might their $\Sigma_2^P$-completeness impact their solvability? 3. What are the implications of the polynomial hierarchy for the development of AI systems, particularly in areas like planning and verification? 4. Explore the concept of the arithmetical hierarchy and its relationship to the polynomial hierarchy. How do these hierarchies inform our understanding of computability and complexity? ::: tcolorbox For the next lecture, please bring your laptops as we will be engaging in hands-on ASP programming exercises. This will provide an opportunity to apply the theoretical concepts discussed today and gain practical experience with logic programming using Answer Set Programming (ASP). :::