<p>A problem $\Pi$ is $\mathsf{NP}$ complete if there is a polynomial time reduction from an $\mathsf{NP}$ complete problem $\Pi^\circ$ to $\Pi$ with polynomial blow up on number of variables and instance size.</p>

<p>What are some examples where the involved polynomial blow up on number of variables is a large degree polynomial (correspondingly giving a large degree polynomial time reduction)?</p>

<p>Reason I am asking is this: suppose someone proves a non-linear lower bound on some NP complete problem, is there a direct way to infer that there is a non-linear lower bound for 3SAT by tracing back reductions?</p>

<p>Related: <a href="https://cstheory.stackexchange.com/questions/21264/natural-candidate-against-the-isomorphism-conjecture">Natural candidate against the Isomorphism Conjecture?</a></p>

CC BY-SA 3.0
2015-07-31T13:36:16.060Z
@RickyDemer Could you please write your answer?
Turbo
CC BY-SA 3.0
2015-08-03T11:09:44.640Z
The usual reduction from SAT to 3-SAT may increase the number of variables exponentially, even though the instance size only increases polynomially, and the polynomial has low degree.  This doesn't give a high-degree polynomial-time reduction.
András Salamon
CC BY-SA 3.0
2015-08-03T11:19:47.793Z
@AndrásSalamon So there is no way to infer non-linear SAT lower bound, unless instance size is linear in blow up? Is there a natural example of a quadratic instance size increment?
Turbo
CC BY-SA 3.0
2015-08-03T13:02:05.520Z
I'm not sure what you regard as natural, but the deterministic time hierarchy theorem guarantees that either there is an infinite hierarchy of problems in P which require larger and larger degrees of the polynomials bounding the number of steps in any many-one reduction of these problems to SAT, or that P ≠ NP.  See also https://constraints.wordpress.com/2010/02/10/pnp-consequences/
András Salamon
CC BY-SA 3.0
2015-08-03T13:05:20.083Z
Of course there are NP-completeness reductions that blow up instance size super-linearly. Since we have not refuted ETH yet, this is true for any reduction for an NP-complete problem with a known $2^{o(n)}$ algorithm. One example is Feedback Arc Set on tournament digraphs, and here are more http://cs.stackexchange.com/a/9817/1490.
Sasho Nikolov
CC BY-SA 3.0
2015-08-03T13:06:05.933Z
@AndrásSalamon I like this post of yours very much. If you may, you could post an excellent answer to this question.
Turbo
<reductions><np-complete>
Will a non-linear lower bound on some NP complete problem prove non-linear lower bound on 3SAT?
Turbo
# Will a non-linear lower bound on some NP complete problem prove non-linear lower bound on 3SAT?

(Asked by: username_0 on 2015-07-31)

A problem $\Pi$ is $\mathsf{NP}$ complete if there is a polynomial time reduction from an $\mathsf{NP}$ complete problem $\Pi^\circ$ to $\Pi$ with polynomial blow up on number of variables and instance size.

What are some examples where the involved polynomial blow up on number of variables is a large degree polynomial (correspondingly giving a large degree polynomial time reduction)?

Reason I am asking is this: suppose someone proves a non-linear lower bound on some NP complete problem, is there a direct way to infer that there is a non-linear lower bound for 3SAT by tracing back reductions?

Related: [Natural candidate against the Isomorphism Conjecture?](https://cstheory.stackexchange.com/questions/21264/natural-candidate-against-the-isomorphism-conjecture)

**Tags:** reductions, np-complete
> **Comments:**
> **username_0**: @RickyDemer Could you please write your answer?  
> **username_1**: The usual reduction from SAT to 3-SAT may increase the number of variables exponentially, even though the instance size only increases polynomially, and the polynomial has low degree.  This doesn't give a high-degree polynomial-time reduction.  
> **username_0**: @AndrásSalamon So there is no way to infer non-linear SAT lower bound, unless instance size is linear in blow up? Is there a natural example of a quadratic instance size increment?  
> **username_1**: I'm not sure what you regard as natural, but the deterministic time hierarchy theorem guarantees that either there is an infinite hierarchy of problems in P which require larger and larger degrees of the polynomials bounding the number of steps in any many-one reduction of these problems to SAT, or that P ≠ NP.  See also https://constraints.wordpress.com/2010/02/10/pnp-consequences/  
> **username_2**: Of course there are NP-completeness reductions that blow up instance size super-linearly. Since we have not refuted ETH yet, this is true for any reduction for an NP-complete problem with a known $2^{o(n)}$ algorithm. One example is Feedback Arc Set on tournament digraphs, and here are more http://cs.stackexchange.com/a/9817/1490.  
> **username_0**: @AndrásSalamon I like this post of yours very much. If you may, you could post an excellent answer to this question.  

---

## 0 answers

