I'll keep the reasoning abstract. If I start from a mathematical formulation of a problem $A$ known to be $NP$-hard, I add a set of constraints which creates a problem $A'$.

However, I do know that there exists some instance of the problem for which the new set of constraint is empty, which brings, for those instance, back to the $NP$-hard formulation.

Is this enough to state that $A'$ is $NP$-hard?

  • 1
    $\begingroup$ To prove that a problem $A$ is NP-hard, we typically pick a problem $B$ already known to be NP-hard, and reduce $B$ to $A$. Try using this proof technique in your case. $\endgroup$ Jul 18 at 10:43
  • $\begingroup$ Thank you, I edited my question. So, can I say that $A'$ is NP-hard because $A$ is $NP$-hard and i can reduce $A$ to $A'$ by simply noticing that $A$ is a case of $A'$ with a set of constraint being empty? $\endgroup$ Jul 18 at 10:58
  • $\begingroup$ If you manage to prove that a problem is NP-hard, then it is NP-hard. $\endgroup$ Jul 18 at 11:08

No (unless $P=NP$), here is a counter-example:

Consider $A:=SAT$. It is well known that this is an NP-complete problem (and hence also an NP-hard problem).

Now, we will add the following constraint: "every $\phi$ with length bigger than $100$ has to have at most $2$ variables in each clause".

For formulas with length less than $100$ the constraint doesn't apply, hence the condition you stated holds.

However, the resulting language is in $P$, since we can reduce it to $2SAT$ which is known to be solved in polynomial time. To do the reduction, simply "brute force" the answer for formulas $\phi$ with length less than $100$, and otherwise keep the formula as-is.

  • $\begingroup$ Thanks for your answer. I feel like we are talking about different kinds of constraint. The one of your examples seems to me that puts a constraint over the existing instances. Instead the constraint I meant reduces only the space of feasible solutions, not the solution space itself. $\endgroup$ Jul 18 at 15:15
  • $\begingroup$ @DanieleCuomo What do you mean by "space of the feasible solutions", and how is that different from the "solution space"? Can you please elaborate a bit more on the differences? $\endgroup$
    – nir shahar
    Jul 18 at 15:41
  • $\begingroup$ For example in the SAT problem, I can find an assignment which does not satisfy all the clauses. In that case the solution is unfeasible, but it is still part of the solution space. $\endgroup$ Jul 18 at 16:11
  • $\begingroup$ How would you define it for an arbitrary language? $\endgroup$
    – nir shahar
    Jul 18 at 16:25
  • $\begingroup$ I would partition the co-domain of the decision variables in two parts. A set of feasible solutions and a set of unfeasible ones. $\endgroup$ Jul 19 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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