<p>First, I agree w/ Ludwik &amp; 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 <span class="math-container">$f$</span>) 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 &quot;up to p-isomorphism, every reduction must have a gadget of this form&quot;, but &quot;up to p-isomorphism&quot; is a pretty hairy equivalence relation to work with at this level.)</p>
<p>But for (ii), I know of one result like this:</p>
<blockquote>
<p>Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf, <a href="http://dx.doi.org/10.1007/978-3-642-32589-2_43" rel="noreferrer">Planarizing Gadgets for Perfect Matching Do Not Exist</a>, MFCS '12.</p>
</blockquote>
<p>I don't think I can do much better than quoting the abstract:</p>
<blockquote>
<p>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.</p>
</blockquote>

CC BY-SA 4.0
2021-05-04T03:56:18.653Z
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.
Cyriac Antony
CC BY-SA 4.0
2021-05-04T03:58:34.530Z
@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.
Joshua Grochow
CC BY-SA 4.0
2021-04-30T16:00:36.887Z
2021-04-30T16:00:36.887Z
Joshua Grochow
<p>I would imagine it very difficult to prove that &quot;[a] certain type of gadget must exist for a reduction from 3-SAT to X&quot;. 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.</p>
<p>If you could indeed prove that <em>every</em> 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.</p>

CC BY-SA 4.0
2021-04-28T11:16:54.710Z
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.
Cyriac Antony
CC BY-SA 4.0
2021-04-29T13:10:38.113Z
"Probably gives evidence" is not a proof, sorry.
Ludwik
CC BY-SA 4.0
2021-04-29T22:29:33.533Z
@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.
Ilkka Törmä
CC BY-SA 4.0
2021-04-30T03:47:28.320Z
@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).
Cyriac Antony
CC BY-SA 4.0
2021-04-28T10:19:19.840Z
2021-04-28T10:19:19.840Z
Ludwik
<p>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.: <a href="https://cs.stackexchange.com/a/132265/78055">Graph Isomorphism</a>).</p>
<p>Is it possible to show that a problem <span class="math-container">$X$</span> is not NP-hard by showing the following?<br />
(i) certain type of gadget must exist for a reduction from 3-SAT to <span class="math-container">$X$</span>, and<br />
(ii) the type of gadget asserted in point (i) cannot exist.</p>
<p>I am afraid such results are not there. Are there at least conjectures that take this direction?</p>

CC BY-SA 4.0
2021-04-28T19:10:09.527Z
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}$?
Jason Gaitonde
CC BY-SA 4.0
2021-04-29T14:07:19.370Z
Sure, $P\neq NP$ is widely believed as opposed to say, ETH (which is used to prove that Graph Isomorphism is not NP-hard).
Cyriac Antony
CC BY-SA 4.0
2021-04-29T20:50:35.230Z
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.
Jason Gaitonde
CC BY-SA 4.0
2021-04-30T03:46:14.800Z
The currently known methods of proving not NP-complete can be found as answer to [this question](https://mathoverflow.net/q/9221/114739).
Cyriac Antony
CC BY-SA 4.0
2021-04-30T14:49:12.490Z
(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.
Joshua Grochow
<np-hardness><reductions>
Proving not NP-complete by non-existence of gadget
Cyriac Antony
# Proving not NP-complete by non-existence of gadget

(Asked by: username_0 on 2021-04-28)

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](https://cs.stackexchange.com/a/132265/78055)).

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?

**Tags:** np-hardness, reductions
> **Comments:**
> **username_1**: 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}$?  
> **username_0**: Sure, $P\neq NP$ is widely believed as opposed to say, ETH (which is used to prove that Graph Isomorphism is not NP-hard).  
> **username_1**: 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.  
> **username_0**: The currently known methods of proving not NP-complete can be found as answer to [this question](https://mathoverflow.net/q/9221/114739).  
> **username_2**: (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.  

---

## 2 answers

### Answer by username_2 on 2021-04-30. Score: 6 | Accepted answer

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](http://dx.doi.org/10.1007/978-3-642-32589-2_43), 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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.  

---

### Answer by username_3 on 2021-04-28. Score: 5

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: "Probably gives evidence" is not a proof, sorry.  
> **username_4**: @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.  
> **username_0**: @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).  

---

