<p>It’s not clear from the question how <span class="math-container">$\Sigma$</span> and <span class="math-container">$L$</span> may depend on the input. E.g., in the mentioned CLIQUE problem, we are given a graph <span class="math-container">$G=(V,E)$</span> as input, and we put <span class="math-container">$\Sigma=V$</span> and <span class="math-container">$L=\{C\subseteq V:\text{$C$ is a clique
of $G$}\}$</span>, both of which depend on <span class="math-container">$G$</span>.</p>
<p>So, to make the question sensible, I am going to assume that given an input <span class="math-container">$w$</span> of length <span class="math-container">$n$</span>, <span class="math-container">$\Sigma$</span> is polynomial-time computable from <span class="math-container">$w$</span> as a list of elements (and in particular, it has size polynomial in <span class="math-container">$n$</span>), and <span class="math-container">$L$</span> is given by a polynomial-time relation <span class="math-container">$R$</span> such that <span class="math-container">$L=\{A\subseteq\Sigma:R(w,A)\}$</span>.</p>
<p>Note that under these conditions, being maximal and being maximum are both decidable in <strong>coNP</strong>. Thus, I’m going to interpret “<strong>NP</strong>-hard” in the question as hardness under poly-time Turing reductions.</p>
<p>Under these conditions, it is easy to construct (artificial) examples where being maximal is <strong>coNP</strong>-complete (thus <strong>NP</strong>-hard under Turing reductions), whereas being maximum is trivially computable in <strong>P</strong>. E.g., given a CNF <span class="math-container">$\phi$</span> in variables <span class="math-container">$\{x_i:0\le i&lt;n\}$</span>, let <span class="math-container">$\Sigma=\{0,\dots,n+3\}$</span>, and let <span class="math-container">$L$</span> consist of the sets
<span class="math-container">$$\begin{align*}
&amp;\{0,\dots,n+2\},\\
&amp;\{n\},\\
&amp;\{i&lt;n:a_i=1\}\cup\{n,n+3\},&amp;&amp;a\in\{0,1\}^n,\phi(a)=1.
\end{align*}$$</span>
Then the only maximum set is <span class="math-container">$\{0,\dots,n+2\}$</span> with <span class="math-container">$n+3$</span> elements, while <span class="math-container">$\{n\}$</span> is maximal iff <span class="math-container">$\phi$</span> is unsatisfiable.</p>

CC BY-SA 4.0
2024-05-15T00:23:16.367Z
Thanks! That's clever :) This is a general pattern I've seen in these cases, where maximum is not just easy but _very_ easy, trivially so perhaps, while a "real" problem is encoded in maximality, in this case (un)satisfiability. Thanks also for trying to make sense of my formalization, it's been a while since I did complexity theory, so I'm sure my use of $\Sigma$ to not-mean an alphabet and $L$ to not-mean a language were confusing!
Federico Lebrón
CC BY-SA 4.0
2024-05-14T06:36:50.237Z
2024-05-14T06:36:50.237Z
Emil Jeřábek
<p><strong>Lemma 1.</strong> <em>There is a language <span class="math-container">$L$</span> (in this case a collection of sets, suitably encoded) such that the problem of deciding whether a given set <span class="math-container">$x$</span> is a maximal element of <span class="math-container">$L$</span> is NP-hard, while the problem of deciding whether a given set <span class="math-container">$x$</span> is a maximum element of <span class="math-container">$L$</span> is in P.</em></p>
<p><em>Proof.</em> Take <span class="math-container">$\cal F$</span> to be the set of finite 3-CNF formulas over the variables <span class="math-container">$x_1, x_2, x_3, \ldots$</span>.  Take <span class="math-container">$\cal N$</span> to be the subset of <span class="math-container">$\cal F$</span> comprised of the formulas in <span class="math-container">$\cal F$</span> that are not satisfiable.  Then take
<span class="math-container">$$L = \big\{\{1, 2, 3\}\big\} \cup \bigcup_{\phi\in \cal F} \big\{\{\phi\}\big\} \cup \bigcup_{\phi\in \mathcal N} \big\{\{\phi, 0\}\big\}.$$</span></p>
<p>Deciding whether a given set is a maximum-size set in <span class="math-container">$A$</span> is easy (the answer is yes iff the set is <span class="math-container">$\{1, 2, 3\}$</span>).
But deciding whether a given set is maximal is NP-hard, by reduction from 3-CNFSAT.  Indeed, a given 3CNF-formula <span class="math-container">$\phi$</span> is satisfiable if and only if <span class="math-container">$\{\phi\}$</span> is maximal in <span class="math-container">$A$</span>. <span class="math-container">$~~~\Box$</span></p>
<p>While I believe this answers OPs question as currently written, it seems likely that that question is not quite what OP intends to ask.  For the record, here is the problem as currently formulated by OP:</p>
<blockquote>
<p>Let <span class="math-container">$\Sigma$</span> be a set, and <span class="math-container">$L \subseteq 2^\Sigma$</span>. We say that an <span class="math-container">$A \in L$</span> is maximal when there does not exist a nonempty <span class="math-container">$B \subseteq \Sigma$</span> such that <span class="math-container">$A \cup B \in L$</span>. Call the set of such maximal subsets <span class="math-container">$m$</span>. We say that <span class="math-container">$A \in L$</span> is maximum if <span class="math-container">$|A| = \max_{B \in L} |B|$</span>. Call the set of such maximum subsets <span class="math-container">$M$</span>. Are there sets <span class="math-container">$\Sigma, L, m, $</span> and <span class="math-container">$M$</span>, such that the decision problem for <span class="math-container">$m$</span> is in NP-hard, but the decision problem for <span class="math-container">$M$</span> is in P?</p>
</blockquote>

CC BY-SA 4.0
2024-05-13T23:42:27.053Z
2024-05-14T10:05:54.840Z
2024-05-14T10:05:54.840Z
Neal Young
<p>For a lot of problems, it's easy to find a maximal solution (say, with a greedy algorithm), but that will in general not be maximum, and in fact computing a maximum solution might be computationally hard. CLIQUE is a classic example of this. Maximum solutions are clearly maximal.</p>
<p>Does the opposite exist? A problem for which determining if a solution is maximum is easy, but determining whether a solution is maximal is hard?</p>
<p>Formally:</p>
<p>Let <span class="math-container">$\Sigma$</span> be a set, and <span class="math-container">$L \subseteq 2^\Sigma$</span>. We say that an <span class="math-container">$A \in L$</span> is maximal when there does not exist a nonempty <span class="math-container">$B \subseteq \Sigma$</span> such that <span class="math-container">$A \cup B \in L$</span>. Call the set of such maximal subsets <span class="math-container">$m$</span>. We say that <span class="math-container">$A \in L$</span> is maximum if <span class="math-container">$|A| = \max_{B \in L} |B|$</span>. Call the set of such maximum subsets <span class="math-container">$M$</span>. Are there sets <span class="math-container">$\Sigma, L, m, $</span> and <span class="math-container">$M$</span>, such that the decision problem for <span class="math-container">$m$</span> is in NP-hard, but the decision problem for <span class="math-container">$M$</span> is in P?</p>

CC BY-SA 4.0
2024-05-12T21:23:52.110Z
Maximality of $A$ should be defined so that $A'\notin L$ for all $A'\supsetneq A$, not just for $A'=A\cup\{\sigma\}$. Besides disagreeing with standard terminology, your definition is also always decidable in P if $L$ is, as you can just check every $\sigma$.
Emil Jeřábek
CC BY-SA 4.0
2024-05-12T21:44:08.713Z
Thanks, I've edited it to use the standard definition.
Federico Lebrón
CC BY-SA 4.0
2024-05-12T23:00:07.697Z
Notation is quite non-standard. Typically $\Sigma$ is a finite alphabet and $L$ is a language which is a subset of all finite length strings ($\Sigma^*$). You have to define maximality with respect to solutions for a given instance which is typically done via relations. As Emil already pointed out, if you are interested at the NP level where checking whether a given string $y$ is a solution to an instance $x$ is easy (poly-time) then finding maximal solutions is going to be easy.
Chandra Chekuri
CC BY-SA 4.0
2024-05-13T03:14:57.840Z
What is the decision problem for $m$ (or for $M$)?  To my understanding, a maximum set is also maximal, so if you can find a maximum one easily, you can find a maximal one easily as well, no?
Manuel Lafond
CC BY-SA 4.0
2024-05-13T06:55:50.163Z
If you are going to write it this way, you need to assume $B\nsubseteq A$, not just that it is nonempty.
Emil Jeřábek
CC BY-SA 4.0
2024-05-13T09:56:15.687Z
Your two definitions use two different orders (the inclusion order, and the order induced by comparisons of the sizes / cardinals) so it might be useful to make that explicit: you are talking about inclusion-maximal and size-maximum.
xavierm02
CC BY-SA 4.0
2024-05-13T12:06:26.290Z
@ManuelLafond “Find XXX” is a *search problem*, not a *decision problem*. Without any information to the contrary, the obvious reading of “decision problem for XXX” is, given an input $x$, decide whether $x$ is XXX. That is, here: given a set $A$ (and perhaps some parameters identifying $\Sigma$ and $L$), decide whether $A$ is a maximal/maximum element of $L$.
Emil Jeřábek
CC BY-SA 4.0
2024-05-13T13:11:29.540Z
If a maximum exists, then any maximal needs to be a maximum. So checking if something is maximal is the same as checking if something is maximum. If a maximum does not exist, then checking if something is maximum is trivial, but checking if something is maximal can be difficult. So just pick an NP-hard problem that does not have maximum solutions.
Kaveh
CC BY-SA 4.0
2024-05-13T16:07:08.763Z
@Kaveh Why is it the case that "any maximal needs to be a maximum"? It could be something cannot be further extended and remain in $L$, and yet is not of a maximum size. Think of a clique which cannot be extended to a clique of maximum size, in a given graph.
Federico Lebrón
CC BY-SA 4.0
2024-05-14T13:31:45.240Z
maximum element needs to be larger than or equal to all other elements, so it needs to be larger than or equal to supposed maximal. if a POSET has a maximum, it cannot have any other maximals.
Kaveh
CC BY-SA 4.0
2024-05-14T13:39:14.937Z
You are not talking about maximum, but maximum size object, which doesn't need to be unique like maximum needs to be. You are using maximum and maximum size as meaning the same thing, but they don't.
Kaveh
CC BY-SA 4.0
2024-05-14T14:37:24.410Z
@Kaveh Whether you like it or not (I’m not a fan of it either), it is a fairly common terminology in combinatorics that “maximal” means maximal wrt inclusion, and “maximum” means maximal wrt size. See e.g. https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definitions .
Emil Jeřábek
CC BY-SA 4.0
2024-05-14T19:21:48.583Z
@EmilJeřábek On the other hand, the usual convention in order theory is that [maximal(a) ↔ ∀x. a ≤ x → x ≤ a] and [maximum(a) ↔ ∀x. x ≤ a].
user76284
CC BY-SA 4.0
2024-05-14T20:09:59.097Z
@user76284 Sure. But so what? The fact that different subfields use conflicting terminology does not make the OP’s terminology wrong. It’s defined in the question.
Emil Jeřábek
CC BY-SA 4.0
2024-05-14T20:13:03.590Z
@EmilJeřábek Right. Just clarifying for other readers.
user76284
<complexity-classes>
Problems where "maximal" is hard, but "maximum" is easy?
Federico Lebrón
# Problems where "maximal" is hard, but "maximum" is easy?

(Asked by: username_0 on 2024-05-12)

For a lot of problems, it's easy to find a maximal solution (say, with a greedy algorithm), but that will in general not be maximum, and in fact computing a maximum solution might be computationally hard. CLIQUE is a classic example of this. Maximum solutions are clearly maximal.

Does the opposite exist? A problem for which determining if a solution is maximum is easy, but determining whether a solution is maximal is hard?

Formally:

Let $\Sigma$ be a set, and $L \subseteq 2^\Sigma$. We say that an $A \in L$ is maximal when there does not exist a nonempty $B \subseteq \Sigma$ such that $A \cup B \in L$. Call the set of such maximal subsets $m$. We say that $A \in L$ is maximum if $|A| = \max\_{B \in L} |B|$. Call the set of such maximum subsets $M$. Are there sets $\Sigma, L, m, $ and $M$, such that the decision problem for $m$ is in NP-hard, but the decision problem for $M$ is in P?

**Tags:** complexity-classes
> **Comments:**
> **username_1**: Maximality of $A$ should be defined so that $A'\notin L$ for all $A'\supsetneq A$, not just for $A'=A\cup\{\sigma\}$. Besides disagreeing with standard terminology, your definition is also always decidable in P if $L$ is, as you can just check every $\sigma$.  
> **username_0**: Thanks, I've edited it to use the standard definition.  
> **username_2**: Notation is quite non-standard. Typically $\Sigma$ is a finite alphabet and $L$ is a language which is a subset of all finite length strings ($\Sigma^*$). You have to define maximality with respect to solutions for a given instance which is typically done via relations. As Emil already pointed out, if you are interested at the NP level where checking whether a given string $y$ is a solution to an instance $x$ is easy (poly-time) then finding maximal solutions is going to be easy.  
> **username_3**: What is the decision problem for $m$ (or for $M$)?  To my understanding, a maximum set is also maximal, so if you can find a maximum one easily, you can find a maximal one easily as well, no?  
> **username_1**: If you are going to write it this way, you need to assume $B\nsubseteq A$, not just that it is nonempty.  
> **username_4**: Your two definitions use two different orders (the inclusion order, and the order induced by comparisons of the sizes / cardinals) so it might be useful to make that explicit: you are talking about inclusion-maximal and size-maximum.  
> **username_1**: @ManuelLafond “Find XXX” is a *search problem*, not a *decision problem*. Without any information to the contrary, the obvious reading of “decision problem for XXX” is, given an input $x$, decide whether $x$ is XXX. That is, here: given a set $A$ (and perhaps some parameters identifying $\Sigma$ and $L$), decide whether $A$ is a maximal/maximum element of $L$.  
> **username_5**: If a maximum exists, then any maximal needs to be a maximum. So checking if something is maximal is the same as checking if something is maximum. If a maximum does not exist, then checking if something is maximum is trivial, but checking if something is maximal can be difficult. So just pick an NP-hard problem that does not have maximum solutions.  
> **username_0**: @Kaveh Why is it the case that "any maximal needs to be a maximum"? It could be something cannot be further extended and remain in $L$, and yet is not of a maximum size. Think of a clique which cannot be extended to a clique of maximum size, in a given graph.  
> **username_5**: maximum element needs to be larger than or equal to all other elements, so it needs to be larger than or equal to supposed maximal. if a POSET has a maximum, it cannot have any other maximals.  
> **username_5**: You are not talking about maximum, but maximum size object, which doesn't need to be unique like maximum needs to be. You are using maximum and maximum size as meaning the same thing, but they don't.  
> **username_1**: @Kaveh Whether you like it or not (I’m not a fan of it either), it is a fairly common terminology in combinatorics that “maximal” means maximal wrt inclusion, and “maximum” means maximal wrt size. See e.g. https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definitions .  
> **username_6**: @EmilJeřábek On the other hand, the usual convention in order theory is that [maximal(a) ↔ ∀x. a ≤ x → x ≤ a] and [maximum(a) ↔ ∀x. x ≤ a].  
> **username_1**: @user76284 Sure. But so what? The fact that different subfields use conflicting terminology does not make the OP’s terminology wrong. It’s defined in the question.  
> **username_6**: @EmilJeřábek Right. Just clarifying for other readers.  

---

## 2 answers

### Answer by username_1 on 2024-05-14. Score: 7 | Accepted answer

It’s not clear from the question how $\Sigma$ and $L$ may depend on the input. E.g., in the mentioned CLIQUE problem, we are given a graph $G=(V,E)$ as input, and we put $\Sigma=V$ and $L=\{C\subseteq V:\text{$C$ is a clique
of $G$}\}$, both of which depend on $G$.

So, to make the question sensible, I am going to assume that given an input $w$ of length $n$, $\Sigma$ is polynomial-time computable from $w$ as a list of elements (and in particular, it has size polynomial in $n$), and $L$ is given by a polynomial-time relation $R$ such that $L=\{A\subseteq\Sigma:R(w,A)\}$.

Note that under these conditions, being maximal and being maximum are both decidable in **coNP**. Thus, I’m going to interpret “**NP**-hard” in the question as hardness under poly-time Turing reductions.

Under these conditions, it is easy to construct (artificial) examples where being maximal is **coNP**-complete (thus **NP**-hard under Turing reductions), whereas being maximum is trivially computable in **P**. E.g., given a CNF $\phi$ in variables $\{x\_i:0\le i, let $\Sigma=\{0,\dots,n+3\}$, and let $L$ consist of the sets
$$\begin{align\*}
&\{0,\dots,n+2\},\\
&\{n\},\\
&\{i
Then the only maximum set is $\{0,\dots,n+2\}$ with $n+3$ elements, while $\{n\}$ is maximal iff $\phi$ is unsatisfiable.

> **Comments:**
> **username_0**: Thanks! That's clever :) This is a general pattern I've seen in these cases, where maximum is not just easy but _very_ easy, trivially so perhaps, while a "real" problem is encoded in maximality, in this case (un)satisfiability. Thanks also for trying to make sense of my formalization, it's been a while since I did complexity theory, so I'm sure my use of $\Sigma$ to not-mean an alphabet and $L$ to not-mean a language were confusing!  

---

### Answer by username_7 on 2024-05-13. Score: 2

**Lemma 1.** *There is a language $L$ (in this case a collection of sets, suitably encoded) such that the problem of deciding whether a given set $x$ is a maximal element of $L$ is NP-hard, while the problem of deciding whether a given set $x$ is a maximum element of $L$ is in P.*

*Proof.* Take $\cal F$ to be the set of finite 3-CNF formulas over the variables $x\_1, x\_2, x\_3, \ldots$. Take $\cal N$ to be the subset of $\cal F$ comprised of the formulas in $\cal F$ that are not satisfiable. Then take
$$L = \big\{\{1, 2, 3\}\big\} \cup \bigcup\_{\phi\in \cal F} \big\{\{\phi\}\big\} \cup \bigcup\_{\phi\in \mathcal N} \big\{\{\phi, 0\}\big\}.$$

Deciding whether a given set is a maximum-size set in $A$ is easy (the answer is yes iff the set is $\{1, 2, 3\}$).
But deciding whether a given set is maximal is NP-hard, by reduction from 3-CNFSAT. Indeed, a given 3CNF-formula $\phi$ is satisfiable if and only if $\{\phi\}$ is maximal in $A$. $~~~\Box$

While I believe this answers OPs question as currently written, it seems likely that that question is not quite what OP intends to ask. For the record, here is the problem as currently formulated by OP:

> Let $\Sigma$ be a set, and $L \subseteq 2^\Sigma$. We say that an $A \in L$ is maximal when there does not exist a nonempty $B \subseteq \Sigma$ such that $A \cup B \in L$. Call the set of such maximal subsets $m$. We say that $A \in L$ is maximum if $|A| = \max\_{B \in L} |B|$. Call the set of such maximum subsets $M$. Are there sets $\Sigma, L, m, $ and $M$, such that the decision problem for $m$ is in NP-hard, but the decision problem for $M$ is in P?


---

