A Proof of P = NP

MONOTONE-MIN-3SAT in Polynomial Time: A Proof of P = NP

Frank Vega
Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA
[e-mail]

Abstract

The P versus NP problem is a cornerstone of theoretical computer science, asking whether problems that are easy to check are also easy to solve. "Easy" here means solvable in polynomial time, where the computation time grows proportionally to the input size. While this problem's origins can be traced to John Nash's 1955 letter, its formalization is credited to Stephen Cook and Leonid Levin. Despite decades of research, a definitive answer remains elusive. Central to this question is the concept of NP-completeness. If even one NP-complete problem could be solved efficiently, it would imply that all NP problems could be solved efficiently, proving $P=NP$ . This research proposes a groundbreaking claim: MONOTONE-MIN-3SAT can be solved in polynomial time and belongs to NP-complete, establishing the equivalence of P and NP.

Keywords: complexity classes; minimum-cut; polynomial time; completeness; reduction

MSC: 68Q15, 68Q17, 05C69, 68Q25

---

1. Introduction

The P versus NP problem is a fundamental question in computer science that asks whether problems whose solutions can be easily checked can also be easily solved [CS00]. "Easily" here means solvable in polynomial time, where the computation time grows proportionally to the input size [CS00, Sun10]. Problems solvable in polynomial time belong to the class P, while NP includes problems whose solutions can be verified efficiently given a suitable "certificate" [CS00, Sun10]. Alternatively, P and NP can be defined in terms of deterministic and non-deterministic Turing machines with polynomial-time complexity [CS00, Sun10].

The central question is whether P and NP are the same. Most researchers believe that P is a strict subset of NP, meaning that some problems are inherently harder to solve than to verify. Resolving this problem has profound implications for fields like cryptography and artificial intelligence [Fort22, Aar16]. The P versus NP problem is widely considered one of the most challenging open questions in computer science. Techniques like relativization and natural proofs have yielded inconclusive results, suggesting the problem's difficulty [Bak75, Raz97]. Similar problems, such as the VP versus VNP problem in algebraic complexity, remain unsolved [Wig19].

The P versus NP problem is often described as a "holy grail" of computer science. A positive resolution could revolutionize our understanding of computation and potentially lead to groundbreaking algorithms for critical problems. The problem is listed among the Millennium Prize Problems. While recent years have seen progress in related areas, such as finding efficient solutions to specific instances of NP-complete problems, the core question of P versus NP remains unanswered [Fort22]. A polynomial-time algorithm for any NP-complete problem would directly imply P equals NP [CLRS01]. Our work focuses on presenting such an algorithm for a new NP-complete problem.

---

2. Background and Ancillary Results

NP-complete problems are the Everest of computational challenges. Despite the ease of verifying proposed solutions with a succinct certificate, finding these solutions efficiently remains an elusive goal. A problem is classified as NP-complete if it satisfies two stringent criteria within computational complexity theory:

1. Efficient Verifiability: Solutions can be quickly checked using a concise proof [CLRS01].
2. Universal Hardness: Every problem in the class NP can be reduced to this problem without significant computational overhead [CLRS01].

The implications of finding an efficient algorithm for a single NP-complete problem are profound. Such a breakthrough would serve as a master key, unlocking efficient solutions for all problems in NP, with transformative consequences for fields like cryptography, artificial intelligence, and planning [Fort22, Aar16].

Illustrative examples of NP-complete problems include:

• Boolean Satisfiability (SAT) Problem: Given a logical expression in conjunctive normal form, determine if there exists an assignment of truth values to its variables that makes the entire expression true [GJ79].
• Boolean 3-Satisfiability (3SAT) Problem: Given a Boolean formula in conjunctive normal form with exactly three literals per clause, determine if there exists a truth assignment to its variables that makes the formula evaluate to true [GJ79].

The provided examples represent a small subset of the extensively studied NP-complete problems relevant to our current work. The satisfiability problem (SAT) is one of the most fundamental problems in computational complexity theory. A Boolean formula $\phi$ is built from:

1. Boolean variables $x_{1}, x_{2}, \ldots, x_{n}$ ;
2. Boolean connectives, i.e., Boolean functions with one or two inputs and one output, such as $\wedge$ (AND), $\lor$ (OR), $\lnot$ (NOT), $\Rightarrow$ (implication), and $\Leftrightarrow$ (if and only if);
3. Parentheses, used to indicate the structure of the formula.

A truth assignment for $\phi$ is a mapping from the variables of $\phi$ to the Boolean values $\{\textit{true}, \textit{false}\}$ . A truth assignment is satisfying if it makes $\phi$ evaluate to true. A Boolean formula is satisfiable if it has at least one satisfying truth assignment. A literal is a Boolean variable or its negation. A Boolean formula is in conjunctive normal form (CNF) if it is a conjunction (AND) of clauses, where each clause is a disjunction (OR) of one or more literals [CLRS01]. The SAT problem asks whether a given Boolean formula in CNF is satisfiable [GJ79]. A 3CNF formula is a CNF formula in which each clause contains exactly three distinct literals [CLRS01]. For example, the following formula is in 3CNF:

$$(x_{1} \lor \lnot x_{2} \lor x_{3}) \wedge (\lnot x_{1} \lor x_{3} \lor x_{2}) \wedge (\lnot x_{1} \lor \lnot x_{3} \lor x_{2}).$$

The first clause $(x_{1} \lor \lnot x_{2} \lor x_{3})$ contains the three literals $x_{1}$ , $\lnot x_{2}$ , and $x_{3}$ . The restriction of SAT to formulas in 3CNF is called 3SAT [CLRS01].

While the classical satisfiability problem seeks to maximize the number of satisfied clauses (or determine if all clauses can be satisfied), the minimum satisfiability problem considers the complementary optimization goal: finding a truth assignment that satisfies as few clauses as possible. Kohli, Krishnamurti, and Mirchandani [kohli1994minimum] introduced the minimum satisfiability problem (MINSAT) and proved that it is NP-hard, even when restricted to formulas where each clause contains at most two literals (MIN-2SAT). Their result established that minimization variants of satisfiability are computationally intractable, contrasting with the polynomial-time solvability of certain restricted satisfiability problems.

In this work, we consider a further restriction that combines two structural constraints: monotonicity and bounded clause size. Monotone SAT variants, where each clause contains only positive literals or only negative literals, have been extensively studied [darmann2021simplified]. These restrictions arise naturally in various applications and exhibit distinct computational properties from their non-monotone counterparts.

We now formalize the variant of interest.

Definition (MONOTONE-MIN-3SAT)

Instance: A Boolean formula $\phi$ in 3CNF such that every clause is monotone (each clause contains either only positive literals or only negative literals) and has three distinct literals, together with a positive integer $k$ .

Question: Does there exist a truth assignment that satisfies at most $k$ clauses?

By presenting the NP-completeness and a polynomial-time solution to MONOTONE-MIN-3SAT, we would establish a proof that P equals NP.

---

3. Main Result

Our main result establishes the computational complexity of this problem.

Theorem 1

MONOTONE-MIN-3SAT is NP-complete.

Proof:

We first show that MONOTONE-MIN-3SAT is in NP. Given a truth assignment for the variables in $\phi$ , we can verify in polynomial time that at most $k$ clauses are satisfied by evaluating each clause under the assignment and counting the number of satisfied clauses. This verification can be done in $O(n \cdot m)$ time, where $n$ is the number of variables and $m$ is the number of clauses.

To show NP-hardness, we reduce from MIN-2SAT, which is NP-complete [kohli1994minimum]. Let $(\psi, k')$ be an instance of MIN-2SAT, where $\psi$ is a Boolean formula in 2CNF over variables $V = \{x_1, x_2, \ldots, x_n\}$ and clauses $C = \{c_1, c_2, \ldots, c_m\}$ , and $k'$ is a positive integer. Each clause $c_i$ has exactly two literals and contains at most one unnegated variable [kohli1994minimum].

We construct an instance $(\phi, k)$ of MONOTONE-MIN-3SAT as follows.

Construction

For each clause $c_i = (\lnot \ell_{i,1} \lor \lnot \ell_{i,2})$ in $\psi$ , introduce fresh variables $y_i, z_i, w_i$ (unique to $c_i$ ), and define three clauses in $\phi$ :

$$\begin{align*} d_{i,1} &= (\lnot \ell_{i,1} \lor \lnot y_i \lor \lnot z_i),\\ d_{i,2} &= (\lnot \ell_{i,2} \lor \lnot y_i \lor \lnot w_i),\\ d_{i,3} &= (y_i \lor z_i \lor w_i). \end{align*}$$

For each clause $c_i = (\ell_{i,1} \lor \lnot \ell_{i,2})$ in $\psi$ , introduce fresh variables $y_i, z_i, w_i, u_i, v_i$ (unique to $c_i$ ), and define three clauses in $\phi$ :

$$\begin{align*} d_{i,1} &= (\ell_{i,1} \lor y_i \lor z_i),\\ d_{i,2} &= (\lnot \ell_{i,2} \lor \lnot w_i \lor \lnot u_i),\\ d_{i,3} &= (y_i \lor w_i \lor v_i). \end{align*}$$

Set

$$k \;=\; m + k'.$$

Gadget Behavior

Fix an assignment $\tau$ on $V$ , and consider a single gadget for $c_i$ :

• If $c_i = (\lnot \ell_{i,1} \lor \lnot \ell_{i,2})$ is unsatisfied by $\tau$ (i.e., both $\lnot \ell_{i,1}$ and $\lnot \ell_{i,2}$ are false under $\tau$ ), then by setting $y_i=z_i=w_i=\text{true}$ , $d_{i,3}$ is satisfied and $d_{i,1}, d_{i,2}$ are unsatisfied; thus exactly one clause is satisfied. Moreover, regardless of how $y_i, z_i, w_i$ are set, at least one of $d_{i,1}, d_{i,2}, d_{i,3}$ is satisfied, so the minimum achievable satisfied count for this gadget is $1$ .

• If $c_i = (\lnot \ell_{i,1} \lor \lnot \ell_{i,2})$ is satisfied by $\tau$ (i.e., at least one of $\lnot \ell_{i,1}, \lnot \ell_{i,2}$ is true under $\tau$ ), then by setting $y_i=z_i=w_i=\text{false}$ , $d_{i,1}$ and $d_{i,2}$ are satisfied and $d_{i,3}$ is unsatisfied; thus exactly two clauses are satisfied. Furthermore, no assignment to $y_i, z_i, w_i$ can make fewer than two of $d_{i,1}, d_{i,2}, d_{i,3}$ satisfied: if $y_i=z_i=w_i=\text{true}$ , then $d_{i,3}$ is satisfied and at least one of $d_{i,1}, d_{i,2}$ is satisfied because at least one of $\lnot \ell_{i,1}, \lnot \ell_{i,2}$ is true. Hence the minimum achievable satisfied count for this gadget is $2$ .

• If $c_i = (\ell_{i,1} \lor \lnot \ell_{i,2})$ is unsatisfied by $\tau$ (i.e., both $\ell_{i,1}$ and $\lnot \ell_{i,2}$ are false under $\tau$ ), then by setting $y_i=z_i=v_i=\text{false}$ ; $w_i=u_i=\text{true}$ , $d_{i,3}$ is satisfied and $d_{i,1}, d_{i,2}$ are unsatisfied; thus exactly one clause is satisfied. Moreover, regardless of how $y_i, z_i, w_i, u_i, v_i$ are set, at least one of $d_{i,1}, d_{i,2}, d_{i,3}$ is satisfied, so the minimum achievable satisfied count for this gadget is $1$ .

• If $c_i = (\ell_{i,1} \lor \lnot \ell_{i,2})$ is satisfied by $\tau$ (i.e., at least one of $\ell_{i,1}, \lnot \ell_{i,2}$ is true under $\tau$ ), then by setting $y_i=w_i=v_i=\text{false}$ ; $z_i=u_i=\text{true}$ , $d_{i,1}$ and $d_{i,2}$ are satisfied and $d_{i,3}$ is unsatisfied; thus exactly two clauses are satisfied. Furthermore, no assignment to $y_i, z_i, w_i, u_i, v_i$ can make fewer than two of $d_{i,1}, d_{i,2}, d_{i,3}$ satisfied: if $y_i=z_i=v_i=\text{false}$ ; $w_i=u_i=\text{true}$ , then $d_{i,3}$ is satisfied and at least one of $d_{i,1}, d_{i,2}$ is satisfied because at least one of $\ell_{i,1}, \lnot \ell_{i,2}$ is true. Hence the minimum achievable satisfied count for this gadget is $2$ .

Therefore, for any fixed assignment on $V$ that satisfies exactly $s$ clauses of $\psi$ , there exists an extension to the auxiliary variables attaining exactly

$$(m-s) \cdot 1 \;+\; s \cdot 2 \;=\; m + s$$

satisfied clauses in $\phi$ , and no extension can attain fewer than $m+s$ .

Correctness

We prove the reduction is correct in both directions.

$(\Rightarrow)$ Suppose $\psi$ has an assignment $\tau$ satisfying at most $k'$ clauses (i.e., $s \le k'$ ). By the gadget behavior, there is an extension $\tau'$ to the auxiliary variables that satisfies exactly $m + s \le m + k' = k$ clauses of $\phi$ . Thus $(\phi, k)$ is a yes-instance of MONOTONE-MIN-3SAT.

$(\Leftarrow)$ Conversely, suppose $(\phi, k)$ is a yes-instance, i.e., there exists an assignment $\tau'$ satisfying at most $k = m + k'$ clauses of $\phi$ . Let $\tau$ be the restriction of $\tau'$ to $V$ , and let $s$ be the number of clauses of $\psi$ satisfied by $\tau$ . By the gadget lower bound, every extension of $\tau$ satisfies at least $m + s$ clauses of $\phi$ , so $m + s \le k = m + k'$ . Therefore $s \le k'$ , and $\psi$ is a yes-instance of MIN-2SAT.

Conclusion

The reduction is polynomial: it introduces a constant number of fresh variables and clauses per original clause. By the two-directional correctness and membership in NP, MONOTONE-MIN-3SAT is NP-complete. $\square$

---

Theorem 2 (Main Insight)

Maximizing the number of unsatisfied clauses in a monotone 2CNF formula (i.e., every clause has the form $(x \lor y)$ or $(\lnot x \lor \lnot y)$ ) can be solved in polynomial time.

Before proving the theorem, we recall some graph-theoretic notions.

Definition (Cut and Minimum Cut)

Let $G = (V, E)$ be an undirected graph with non-negative edge weights.

• A cut is a partition of $V$ into two disjoint sets $S$ and $T = V \setminus S$ .
• The weight of the cut $(S, T)$ is the sum of the weights of all edges with one endpoint in $S$ and the other in $T$ .
• A minimum cut (or min-cut) is a cut of minimum weight. Its value is denoted by $\lambda(G)$ .

The global minimum cut of a graph can be computed in polynomial time; for example, the deterministic algorithm of Stoer and Wagner [StoerWagner97, networkx_stoer_wagner] runs in

$$O\bigl(|V|\,(|E| + |V|)\,\log |V|\bigr).$$

Proof of Theorem 2:

Let $\Phi$ be a monotone 2CNF formula with clause set

$$\mathcal{C} = \mathcal{C}^+ \cup \mathcal{C}^-,$$

where

• $\mathcal{C}^+$ consists of clauses of the form $(x \lor y)$ ,
• $\mathcal{C}^-$ consists of clauses of the form $(\lnot x \lor \lnot y)$ .

Let $V$ be the set of variables of $\Phi$ , and let $m = |\mathcal{C}|$ be the total number of clauses.

Graph Construction

Build an undirected graph $G = (V, E)$ as follows:

• For each clause $(x \lor y) \in \mathcal{C}^+$ , add edge $\{x, y\}$ of weight $1$ .
• For each clause $(\lnot x \lor \lnot y) \in \mathcal{C}^-$ , add edge $\{x, y\}$ of weight $1$ .

When parallel edges occur, they are merged into one edge whose weight equals their multiplicity. For instance, the presence of both $(x \lor y) \in \mathcal{C}^+$ and $(\lnot x \lor \lnot y) \in \mathcal{C}^-$ results in an edge $\{x, y\}$ with weight $2$ .

Assignment and Cut

Fix a truth assignment $\tau : V \to \{\text{true}, \text{false}\}$ and define the cut

$$S = \{ v \in V : \tau(v) = \text{false} \}, \qquad T = \{ v \in V : \tau(v) = \text{true} \}.$$

Unsatisfied Clauses

A clause is unsatisfied under $\tau$ exactly when both literals evaluate to false:

• $(x \lor y)$ is unsatisfied iff $x, y \in S$ ,
• $(\lnot x \lor \lnot y)$ is unsatisfied iff $x, y \in T$ .

In both cases, the corresponding edge $\{x, y\}$ lies entirely within one side of the cut and does not cross $(S, T)$ .

Thus,

$$\#\{\text{unsatisfied clauses}\} = m - \text{weight}(S, T).$$

Optimization Equivalence

Maximizing the number of unsatisfied clauses is equivalent to minimizing the cut weight:

$$\max_{\tau} \#\{\text{unsatisfied clauses under } \tau\} = m - \lambda(G).$$

An optimal assignment is obtained from any minimum cut $(S, T)$ by setting all variables in $S$ to false and all variables in $T$ to true (or vice versa). Since $G$ has $O(m)$ edges and $\lambda(G)$ can be computed in polynomial time, the problem is solvable in polynomial time. $\square$

Remark: This reduction shows that the optimization problem is equivalent to computing the ground state of a ferromagnetic Ising model without external field on an arbitrary graph [Barahona82]. In the unweighted case, it coincides with the minimum graph bisection problem.

---

Theorem 3

The problem MONOTONE-MIN-3SAT can be solved in polynomial time.

Proof:

Consider a monotone 3CNF formula and a single positive clause

$$c_i = (x \lor y \lor z).$$

By Theorem 2, maximizing the number of unsatisfied clauses in a monotone 2CNF formula (clauses of the form $(x \lor y)$ or $(\lnot x \lor \lnot y)$ ) is solvable in polynomial time. We reduce MONOTONE-MIN-3SAT to this problem by replacing each clause $c_i$ with a small monotone 2CNF gadget whose maximum number of unsatisfied clauses reflects whether $c_i$ is satisfied.

Positive Clause Gadget

For $(x \lor y \lor z)$ , introduce auxiliary variables $x_i, y_i, z_i, w_i$ and a pivot variable $w$ . Define

$$r(x,y,z,w) = \bigwedge_{j=1}^{10} C_j,$$

where the clauses are:

$$\begin{align*} &(x \lor x_i), \quad (y \lor y_i), \quad (z \lor z_i), \quad (\lnot w \lor \lnot w_i),\\ &(\lnot x \lor \lnot y), \quad (\lnot y \lor \lnot z), \quad (\lnot z \lor \lnot x),\\ &(x \lor w), \quad (y \lor w), \quad (z \lor w). \end{align*}$$

Fix $x_i=y_i=z_i=\text{false}$ and analyze the minimum number of satisfiable clauses:

• All $x,y,z$ true: $w=\text{true}$ yields 6 satisfied clauses; $w=\text{false}$ yields 7. Minimum: 6.
• Exactly two true: Both $w=\text{true}$ and $w=\text{false}$ yield 7. Minimum: 7.
• Exactly one true: $w=\text{false}$ yields 6; $w=\text{true}$ yields 7. Minimum: 6.
• All false: $w=\text{false}$ yields 4; $w=\text{true}$ yields 6. Minimum: 4.

Thus:

$$\#\text{maximum unsat} = \begin{cases} 4 & \text{if $(x \lor y \lor z)$ is satisfied},\\ 6 & \text{if $(x \lor y \lor z)$ is unsatisfied}. \end{cases}$$

Negative Clause Gadget

For $(\lnot x \lor \lnot y \lor \lnot z)$ , introduce $x_i, y_i, z_i, w_i, w$ and define:

$$\begin{align*} &(\lnot x \lor \lnot x_i), \quad (\lnot y \lor \lnot y_i), \quad (\lnot z \lor \lnot z_i), \quad (w \lor w_i),\\ &(x \lor y), \quad (y \lor z), \quad (z \lor x),\\ &(\lnot x \lor \lnot w), \quad (\lnot y \lor \lnot w), \quad (\lnot z \lor \lnot w). \end{align*}$$

A symmetric case analysis shows the same gap: 4 maximum unsatisfied clauses if the original clause is satisfied, 6 if unsatisfied.

Global Construction

Form a 2CNF formula $R$ by replacing each clause of the original monotone 3CNF with its gadget. The size of $R$ is linear in the original formula.

Each clause contributes either 4 or 6 maximum unsatisfied gadget clauses depending on satisfaction. Hence maximizing unsatisfied clauses in $R$ is equivalent (up to an additive constant) to maximizing unsatisfied clauses in the original formula. Since the former is solvable in polynomial time, so is the latter.

Therefore, MONOTONE-MIN-3SAT is solvable in polynomial time. $\square$

---

Theorem 4 (Main Theorem)

$P = NP$ .

Proof:

This is a direct consequence of Theorems 1, 2, and 3. $\square$

---

4. Conclusion

A definitive proof that P equals NP would fundamentally reshape our computational landscape. The implications of such a discovery are profound and far-reaching:

Algorithmic Revolution

The most immediate impact would be a dramatic acceleration of problem-solving capabilities. Complex challenges currently deemed intractable, such as protein folding, logistics optimization, and certain cryptographic problems, could become efficiently solvable [Fort22, Aar16]. This breakthrough would revolutionize fields from medicine to cybersecurity. Moreover, everyday optimization tasks, from scheduling to financial modeling, would benefit from exponentially faster algorithms, leading to improved efficiency and decision-making across industries [Fort22, Aar16].

Scientific Advancements

Scientific research would undergo a paradigm shift. Complex simulations in fields like physics, chemistry, and biology could be executed at unprecedented speeds, accelerating discoveries in materials science, drug development, and climate modeling [Fort22, Aar16]. The ability to efficiently analyze massive datasets would provide unparalleled insights in social sciences, economics, and healthcare, unlocking hidden patterns and correlations [Fort22, Aar16].

Technological Transformation

Artificial intelligence would be profoundly impacted. The development of more powerful AI algorithms would be significantly accelerated, leading to breakthroughs in machine learning, natural language processing, and robotics [Fort22, Aar16]. While the cryptographic landscape would face challenges, it would also present opportunities to develop new, provably secure encryption methods [Fort22, Aar16].

Economic and Societal Benefits

The broader economic and societal implications are equally significant. A surge in innovation across various sectors would be fueled by the ability to efficiently solve complex problems. Resource optimization, from energy to transportation, would become more feasible, contributing to a sustainable future [Fort22, Aar16].

In conclusion, a proof of $P = NP$ would usher in a new era of computational power with transformative effects on science, technology, and society. While challenges and uncertainties exist, the potential benefits are immense, making this a compelling area of continued research.

---

References

• [CLRS01] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to Algorithms (2nd ed.). MIT Press.

• [GJ79] Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.

• [kohli1994minimum] Kohli, R., Krishnamurti, R., & Mirchandani, P. (1994). The Minimum Satisfiability Problem. SIAM Journal on Discrete Mathematics, 7(2), 275-283. DOI: 10.1137/S0895480191220836

• [darmann2021simplified] Darmann, A., & Döcker, J. (2021). On Simplified NP-Complete Variants of Monotone 3-Sat. Discrete Applied Mathematics, 292, 45-58. DOI: 10.1016/j.dam.2020.12.010

• [CS00] Cook, S. A. (2022, June). The P versus NP Problem. Clay Mathematics Institute. Retrieved from https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf (Accessed: December 4, 2025)

• [Sun10] Sudan, M. (2010, May). The P vs. NP problem. Retrieved from http://people.csail.mit.edu/madhu/papers/2010/pnp.pdf (Accessed: December 4, 2025)

• [Aar16] Aaronson, S. (2016). $P \mathop{=}\limits^{?} NP$ . In Open Problems in Mathematics (pp. 1-122). Springer. DOI: 10.1007/978-3-319-32162-2_1

• [Fort22] Fortnow, L. (2022). Fifty years of P vs. NP and the possibility of the impossible. Communications of the ACM, 65(1), 76-85. DOI: 10.1145/3460351

• [Bak75] Baker, T., Gill, J., & Solovay, R. (1975). Relativizations of the $\mathcal{P=?NP}$ Question. SIAM Journal on Computing, 4(4), 431-442. DOI: 10.1137/0204037

• [Raz97] Razborov, A. A., & Rudich, S. (1997). Natural Proofs. Journal of Computer and System Sciences, 55(1), 24-35. DOI: 10.1006/jcss.1997.1494

• [StoerWagner97] Stoer, M., & Wagner, F. (1997). A Simple Min-Cut Algorithm. Journal of the ACM, 44(4), 585-591. DOI: 10.1145/263867.263872

• [Barahona82] Barahona, F. (1982). On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15(10), 3241-3253. DOI: 10.1088/0305-4470/15/10/028

• [Wig19] Wigderson, A. (2019). Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press.

• [networkx_stoer_wagner] NetworkX Developers. (2025). NetworkX: stoer_wagner. NetworkX 3.6 documentation. Retrieved from https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.connectivity.stoerwagner.stoer_wagner.html (Accessed: December 4, 2025)

---

MSC (2020): 68Q15 (Complexity classes), 68Q17 (Computational difficulty of problems), 05C69 (Vertex subsets with special properties), 68Q25 (Analysis of algorithms and problem complexity)

---

Documentation

Available as PDF at MONOTONE-MIN-3SAT in Polynomial Time: A Proof of P = NP.