7
$\begingroup$

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?

$\endgroup$
15
  • 1
    $\begingroup$ 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$. $\endgroup$ May 12 at 21:23
  • 2
    $\begingroup$ 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. $\endgroup$ May 12 at 23:00
  • 4
    $\begingroup$ 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? $\endgroup$ May 13 at 3:14
  • 1
    $\begingroup$ @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$. $\endgroup$ May 13 at 12:06
  • 2
    $\begingroup$ @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. $\endgroup$ May 13 at 16:07

2 Answers 2

7
$\begingroup$

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<n\}$, let $\Sigma=\{0,\dots,n+3\}$, and let $L$ consist of the sets $$\begin{align*} &\{0,\dots,n+2\},\\ &\{n\},\\ &\{i<n:a_i=1\}\cup\{n,n+3\},&&a\in\{0,1\}^n,\phi(a)=1. \end{align*}$$ Then the only maximum set is $\{0,\dots,n+2\}$ with $n+3$ elements, while $\{n\}$ is maximal iff $\phi$ is unsatisfiable.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ May 15 at 0:23
2
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.