# Will a non-linear lower bound on some NP complete problem prove non-linear lower bound on 3SAT?

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?

• circuit-SAT to formula-SAT $\;$ – user6973 Jul 31 '15 at 13:32
• 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 Aug 3 '15 at 11:09
• 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 constraints.wordpress.com/2010/02/10/pnp-consequences – András Salamon Aug 3 '15 at 13:02
• 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 cs.stackexchange.com/a/9817/1490. – Sasho Nikolov Aug 3 '15 at 13:05

The reduction from circuit-SAT to formula-SAT increases the number of variables
by the number of internal gates, since it is also a reduction to CNF-SAT.

It creates a new variable for each internal gate and creates

$\;\;\;$ one or more clauses asserting the truth of the circuit's output
$\;\;\;\;\;\;\;\;$ and
$\;\;\;$ the clauses $\:$ (input or output) , ((not input) or not output) $\:$ for each NOT gate
$\;\;\;\;\;\;\;\;$ and
$\;\;\;$ clauses $\:$ (i_0 or i_1 or ... or i_(fanin-1) or not output) , (output or not i_0)
$\;\;\;$ , (output or not i_1) , ... , (output or not i_(fanin-1)) $\:$ for each OR gate
$\;\;\;\;\;\;\;\;$ and
$\;\;\;$ clauses $\:$ ((not i_0) or (not i_1) or ... or (not i_(fanin-1)) or output) , (i_0 or not output)
$\;\;\;$ , (i_1 or not output) , ... , (i_(fanin-1) or not output) $\:$ for each AND gate

.

However, that reduction does not blowup instance size.

• Do you know the exact numbers (mathematical details) by which the blow up occurs? – Turbo Jul 31 '15 at 14:25
• The exact numbers are "the number of internal gates". $\:$ What do you men by "mathematical details"? $\;\;\;\;$ – user6973 Jul 31 '15 at 14:26
• number of gates is what function of variables? is it quadratic? – Turbo Jul 31 '15 at 14:33
• If fanin is at most 2 then number of internal gates is at least [number of variables minus 2]. $\:$ Otherwise, number of gates is completely independent of number of variables. $\;\;\;\;$ – user6973 Jul 31 '15 at 14:41
• This is just a linear blow up then. – Turbo Jul 31 '15 at 14:43