Difficulty: Intermediate | Prerequisites: Understanding of P and NP definitions, polynomial-time Turing machines, basic set operations (union, intersection, complement, concatenation).
Closure properties tell you what operations you can perform on languages in a complexity class without leaving that class. They are fundamental to the structure of complexity theory: if P is closed under intersection, then combining two polynomial-time problems gives you another polynomial-time problem.
This section of the course also introduces coNP (the complement class of NP) and explores what happens if P equals NP. These results tie together the machinery of Turing machines, verifiers, and set operations in a way that exam questions love to test.
You should be comfortable with the definitions of P and NP, and with constructing Turing machines and verifiers from the companion notes on NP membership.
P is closed under intersection, union, concatenation, and complement. NP is closed under union (and intersection, though that is not covered here). If P = NP, then NP is also closed under complement, which means NP = coNP. These proofs all follow the same recipe: take the machines or verifiers for the individual languages and combine them into a new machine or verifier for the resulting language.
Closure property
A complexity class C is closed under an operation (e.g. union) if applying that operation to any languages in C always produces another language in C.
In simple terms, "closed under union" means: take any two problems the class can handle, combine them with OR, and the class can still handle the result.
Complement of a language (L̄)
The set of all strings not in L. If L is the set of prime numbers, L̄ is the set of non-prime numbers.
coNP
The class of languages whose complements are in NP. Equivalently, L ∈ coNP if and only if L̄ ∈ NP.
Think of it as: NP captures problems where "yes" answers have short proofs. coNP captures problems where "no" answers have short proofs.
Concatenation of languages (AB)
The set of all strings that can be split into a prefix in A followed by a suffix in B. Formally: AB = { xy : x ∈ A, y ∈ B }.
P = NP (hypothesis)
The conjecture (widely believed to be false) that every problem whose solutions can be verified quickly can also be solved quickly. If true, it collapses the distinction between P, NP, and coNP.
Given A, B ∈ P with polynomial-time deciders M_A and M_B, construct M' that decides A ∩ B.
Construction: M' on input w:
Run M_A(w). If it rejects, reject.
Run M_B(w). If it rejects, reject.
If both accept, accept.
Correctness: w ∈ A ∩ B if and only if both M_A and M_B accept, which is exactly when M' accepts.
Time complexity: M_A runs in O(n^a) and M_B in O(n^b). M' runs both sequentially, so it runs in O(n^a + n^b) = O(n^max(a,b)), which is polynomial.
Note: the homework solution text mentions "union" in its correctness argument, but the construction (accept only if both accept) is correct for intersection.
Given A, B ∈ NP with polynomial-time verifiers V_A and V_B, construct a verifier M' for A ∪ B.
Construction: M' on input ⟨w, c⟩:
Run V_A(w, c). If it accepts, accept.
Run V_B(w, c). If it accepts, accept.
Otherwise, reject.
Correctness: if w ∈ A ∪ B, then w is in at least one of A or B, so a valid certificate exists for V_A or V_B, and M' accepts. If w is in neither, no certificate makes either verifier accept, so M' rejects.
Time complexity: V_A and V_B are both polynomial-time verifiers. Running them sequentially keeps M' in polynomial time.
Given A, B ∈ P with polynomial-time deciders M_A and M_B, construct M' that decides AB (the concatenation).
Construction: M' on input w:
For every index i from 0 to |w|, split w into a prefix w[0..i] and a suffix w[i+1..n].
For each split, run M_A on the prefix and M_B on the suffix.
If any split causes both M_A and M_B to accept, accept.
If no split works, reject.
(This includes the boundary cases: M_A on the empty string with M_B on all of w, and M_A on all of w with M_B on the empty string.)
Correctness: w ∈ AB if and only if some partition of w has its prefix in A and suffix in B. M' tries all |w| + 1 partitions, so it finds the right one if it exists.
Time complexity: there are O(n) possible splits. Each split runs M_A and M_B, each in polynomial time. So the total is O(n) × poly(n) = poly(n). Still polynomial.
Given L ∈ P with a polynomial-time decider M, construct M' that decides L̄.
Construction: M' on input w:
Run M on w.
If M accepts, reject. If M rejects, accept.
Correctness: M' accepts exactly the strings M rejects, which are the strings not in L. So M' decides L̄.
Time complexity: M runs in polynomial time, and M' does exactly the same computation plus one flip of the answer. Still polynomial.
This proof is straightforward because deterministic TMs give a definitive accept/reject on every input. The same argument does not obviously work for NP, because a nondeterministic verifier's "reject" means "no certificate works," and flipping that does not give you a certificate for the complement.
This proof chains together two facts.
Assumption: P = NP.
Argument:
From part 4a, P is closed under complement.
If P = NP, then every language in NP is also in P.
Take any L ∈ NP. By the assumption, L ∈ P.
Since P is closed under complement, L̄ ∈ P.
Since P = NP, L̄ ∈ NP.
So for every L in NP, L̄ is also in NP. That means NP is closed under complement.
The link to coNP: L̄ ∈ NP is exactly the definition of L ∈ coNP. So every language in NP is also in coNP, and vice versa.
This is the full conclusion, tying together the earlier parts.
Argument:
For every L ∈ NP: L ∈ P (by P = NP), so L̄ ∈ P (P closed under complement), so L̄ ∈ NP (by P = NP). Since L̄ ∈ NP, we have L ∈ coNP. Therefore NP ⊆ coNP.
For every L ∈ coNP: by definition, L̄ ∈ NP, so L̄ ∈ P (by P = NP), so L ∈ P (P closed under complement), so L ∈ NP (by P = NP). Therefore coNP ⊆ NP.
Combining both directions: NP = coNP.
This is a conditional result. Whether P actually equals NP remains one of the biggest open questions in mathematics and computer science. The consensus is that P ≠ NP, which would mean NP and coNP are likely distinct.
Students often confuse closure under intersection with closure under union. For intersection, M' accepts only if both sub-machines accept. For union, M' accepts if either accepts. Getting the logic wrong inverts the proof.
A frequent error in the concatenation proof is forgetting to try all possible split points, including the empty-string boundaries. You must test every partition of the input.
Students sometimes assume NP is closed under complement without justification. This is an open question (equivalent to asking whether NP = coNP). You can only conclude it under the additional assumption that P = NP.
In the complement proof for P, students sometimes try to use a nondeterministic TM. The proof works precisely because P uses deterministic TMs, which always halt with a definitive accept or reject.
⚠️ Closure proofs follow a template: state the given machines/verifiers, construct the new machine, prove correctness (both directions), and analyse time complexity. Know this template cold.
⚠️ The complement question is a favourite exam topic because the answer differs for P (yes, always) and NP (unknown, unless P = NP). Be ready to explain why the simple flip-the-answer trick works for P but not NP.
⚠️ The concatenation proof requires the most care. Make sure you can explain why trying all O(n) splits keeps the algorithm in polynomial time.
⚠️ "If P = NP, then NP = coNP" is a conditional proof. Exams may ask you to prove it and separately ask whether the converse holds. (It does not obviously hold.)
True or False: P is closed under complement. ___
True or False: NP is known to be closed under complement (without assuming P = NP). ___
Fill in the blank: To prove P is closed under concatenation, M' tries all ___ possible split points of the input.
True or False: If P = NP, then NP = coNP. ___
Fill in the blank: L ∈ coNP means ___ ∈ NP.
Answers: 1. True. 2. False (this is an open question). 3. |w| + 1 (or O(n)). 4. True. 5. L̄ (the complement of L).
Q: Prove that P is closed under intersection. State the construction, correctness, and time analysis.
A: Given deciders M_A and M_B for A and B in P, construct M' that runs M_A(w) then M_B(w) and accepts only if both accept. Correctness: w ∈ A ∩ B iff both accept. Time: O(n^a + n^b), polynomial.
Q: Why can you not use the same "flip the answer" technique to prove NP is closed under complement?
A: An NP verifier accepts when some certificate works. "No certificate works" (rejection) is not something you can verify with a single certificate. Flipping accept/reject on a verifier does not produce a valid verifier for the complement language, because the verifier's structure is asymmetric: it confirms existence, not non-existence.
Q: Prove that P is closed under concatenation.
A: Given M_A and M_B for A and B in P, construct M' that tries every split of the input w into a prefix x and suffix y, running M_A(x) and M_B(y). Accept if any split makes both accept; reject if none does. There are O(n) splits, each checked in polynomial time, so the total is polynomial.
Q: Assuming P = NP, prove that NP = coNP.
A: Take any L ∈ NP. By P = NP, L ∈ P. Since P is closed under complement, L̄ ∈ P = NP, so L ∈ coNP. Thus NP ⊆ coNP. Symmetrically, take L ∈ coNP: L̄ ∈ NP = P, so L ∈ P = NP. Thus coNP ⊆ NP. Combined: NP = coNP.
Closure properties are the bridge between individual complexity results and the structure of complexity classes as a whole. They explain, for example, why you can freely combine polynomial-time subroutines inside a larger polynomial-time algorithm.
The coNP material connects to NP-completeness: if any NP-complete problem is also in coNP, then NP = coNP. This is one of the structural consequences that makes NP-completeness such a powerful concept.
The P = NP assumption in problems 4b and 4c connects to virtually every major open question in complexity theory, cryptography, and optimisation.
closure property complexity class, P closed under intersection, P closed under union, P closed under complement, P closed under concatenation, NP closed under union, coNP, NP equals coNP, P equals NP implications, complement of a language, deterministic TM complement, EECS 376, Foundations of Computer Science, University of Michigan, complexity class operations, language operations, polynomial-time closure