2
$\begingroup$

Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if the problem under consideration is NP-hard, then some widely believed complexity assumption fails (e.g.: Graph Isomorphism).

Is it possible to show that a problem $X$ is not NP-hard by showing the following?
(i) certain type of gadget must exist for a reduction from 3-SAT to $X$, and
(ii) the type of gadget asserted in point (i) cannot exist.

I am afraid such results are not there. Are there at least conjectures that take this direction?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Doing so unconditionally already implies $\mathsf{P}\neq \mathsf{NP}$, so are you specifically interested in proving that a problem is not $\mathsf{NP}$-hard under the condition that $\mathsf{P}\neq \mathsf{NP}$? $\endgroup$
    – Jason Gaitonde
    Apr 28, 2021 at 19:10
  • $\begingroup$ Sure, $P\neq NP$ is widely believed as opposed to say, ETH (which is used to prove that Graph Isomorphism is not NP-hard). $\endgroup$
    – Cyriac Antony
    Apr 29, 2021 at 14:07
  • 1
    $\begingroup$ I think more people believe GI isn't NP-hard because it collapses $\mathsf{PH}$ to the second level, which is barely more believable than $\mathsf{P}= \mathsf{NP}$. In any event, it's hard for me to see how assuming $\mathsf{P}\neq \mathsf{NP}$ helps specifically with respect to directly arguing about the nature of possible gadgets (obviously one could very indirectly rule them out by showing $\mathsf{NP}$-hardness implies $\mathsf{P}=\mathsf{NP}$ by other means). Of course, that doesn't mean it's impossible, just that that may be a reason such results are not there. $\endgroup$
    – Jason Gaitonde
    Apr 29, 2021 at 20:50
  • $\begingroup$ The currently known methods of proving not NP-complete can be found as answer to this question. $\endgroup$
    – Cyriac Antony
    Apr 30, 2021 at 3:46
  • $\begingroup$ (i) sounds hard and probably just false - reductions (ie, polytime algorithms satisfying certain input-output constraints) are just too varied. But for (ii) I have actually seen such results, I'll have to see if I can find them. $\endgroup$
    – Joshua Grochow
    Apr 30, 2021 at 14:49

2 Answers 2

Reset to default
6
$\begingroup$

First, I agree w/ Ludwik & other comments that I think (i) is unlikely. Polynomial-time reductions are just polynomial-time algorithms satisfying a certain (fairly flexible! compared to say p-time algorithms computing a fixed function $f$) input-output relationship, and polynomial-time algorithms are just too varied to say that they must take a certain form. You can always compose a gadget-based reduction with a p-automorphism to get something that does not recognizably have gadgets anywhere. (So at the very least you probably want to say "up to p-isomorphism, every reduction must have a gadget of this form", but "up to p-isomorphism" is a pretty hairy equivalence relation to work with at this level.)

But for (ii), I know of one result like this:

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf, Planarizing Gadgets for Perfect Matching Do Not Exist, MFCS '12.

I don't think I can do much better than quoting the abstract:

To reduce a graph problem to its planar version, a standard technique is to replace crossings in a drawing of the input graph by planarizing gadgets. We show unconditionally that such a reduction is not possible for the perfect matching problem and also extend this to some other problems related to perfect matching. We further show that there is no planarizing gadget for the Hamiltonian cycle problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Since perfect matching is in P, I was wondering why this result is relevant. They are interested in whether planar perfect matching is in NC. $\endgroup$
    – Cyriac Antony
    May 4, 2021 at 3:56
  • $\begingroup$ @Cyriac Antony: It is not relevant to the question of NP. It is relevant to the question of proving that gadgets of some kind don't exist. It is the only example I know of such a proof. $\endgroup$
    – Joshua Grochow
    May 4, 2021 at 3:58
5
$\begingroup$

I would imagine it very difficult to prove that "[a] certain type of gadget must exist for a reduction from 3-SAT to X". You could state that one type of gadget would enable a specific reduction, or even a family of reductions, but there might still be a different reduction possible that you haven't thought of.

If you could indeed prove that every reduction requires your gadget, and this gadget does not exist, then that sounds like a valid argument, but I don't know how you would ever get there.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I shall give an 'example' of what I mean. Most reductions use the 'duplication' gadget; that is, a gadget that duplicates a specific attribute (such as truth value, color, etc.). Even when a reduction does not employ a gadget of this type, it is often possible to construct it from the actual gadgets used. So, if we can show that a 'duplication' gadget cannot exist, it probably gives an evidence that the problem is not NP-hard. $\endgroup$
    – Cyriac Antony
    Apr 28, 2021 at 11:16
  • $\begingroup$ "Probably gives evidence" is not a proof, sorry. $\endgroup$
    – Ludwik
    Apr 29, 2021 at 13:10
  • 4
    $\begingroup$ @CyriacAntony Not long ago I was working on a P-completeness proof related to certain finite automata. Our first few approaches failed, and in fact we proved that in our attempted reductions, either duplication gadgets or or-gate gadgets didn't exist. Nevertheless, we eventually found a reduction using gadgets that run "backwards in time." Intuitively, our or-gadget transforms an input $x$ non-deterministically into any pair $(y,z)$ with $x = y \vee z$. The moral of this story is that such evidence can point in the wrong direction and there are infinitely many "attributes" you can work with. $\endgroup$
    – Ilkka Törmä
    Apr 29, 2021 at 22:29
  • $\begingroup$ @IlkkaTörmä Thank you for your comment. I should have asked about duplication gadget in the question itself. It is great to know that you think there are infinitely many attributes to work with. I am interested in proof/evidence for this (should be possible as gadgets are finally defined formally). $\endgroup$
    – Cyriac Antony
    Apr 30, 2021 at 3:47

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.