NP-completeness and changing it for a decision problem

Question

If we have a Np-Complete decision problem like independent set or finding matching in graph theory and we change the greatness or smallness of the condition of that problem i.e. change the direction of angle bracket in that condition ($\ge or \le$) for example in independent set problem when the condition is $|V'| \ge k$ and I change it into $|V'| \le k $, are these changed problems like the above still np-complete ???

Answer 1

Probably not, but the truth of this is not known.

Note that essentially the $\ge$ problem is the negation of the $\le$ problem, modulo some trivial preprocessing on the bound you input.

If P=NP, then the NP-complete problems are exactly those that are in P (and are not trivial), and in that case switching $\le$ to $\ge$ is not going to take the problem out of the class. So you should not hope to find a problem where you can prove that switching $\le$ to $\ge$ produces something that is not NP-complete.

On the other hand, if you have proved the $\le$ problem to be NP-complete, then you shouldn't expect to be able to prove that the $\ge$ problem is even in NP -- because such a proof, even for a single problem, would imply that NP=coNP, which is itself a famous open question.

Answer 2

In contrast to my former understanding of your question, all of this seems to have nothing to do with $\mathrm{co}$-$\mathrm{NP}$, etc. Instead I believe the answer to your question depends highly on the exact problem given. Of course, if there are trivial examples of the structures in question, like matchings (one edge) or independent sets (one vertex), then the "relation-inversed" variations are completely trivial to solve.

On the other hand, if you have an already hard problem on the existence of some structure (for example a graph isomorphism), and you add an additional assumption in the form of a lower bound that must be exceeded, exchanging the lower bound by an upper bound will not necessarily make the problem any easier. The hard core, the question of existence, is unchanged.

Actually, at this moment, I am lacking concrete formal examples where I can be sure that reversing the inequality will not change the situation. But I hope the idea was made clear.

---

Thanks to Fabio, who pointed out that CNF SAT (Conjunctive normal form satisfiability) is an example for such a problem. See his comment.