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?

  • $\begingroup$ circuit-SAT to formula-SAT $\;$ $\endgroup$ – user6973 Jul 31 '15 at 13:32
  • $\begingroup$ @RickyDemer Could you please write your answer? $\endgroup$ – Brout Jul 31 '15 at 13:36
  • $\begingroup$ 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. $\endgroup$ – András Salamon Aug 3 '15 at 11:09
  • 1
    $\begingroup$ 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 $\endgroup$ – András Salamon Aug 3 '15 at 13:02
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Do you know the exact numbers (mathematical details) by which the blow up occurs? $\endgroup$ – Brout Jul 31 '15 at 14:25
  • $\begingroup$ The exact numbers are "the number of internal gates". $\:$ What do you men by "mathematical details"? $\;\;\;\;$ $\endgroup$ – user6973 Jul 31 '15 at 14:26
  • $\begingroup$ number of gates is what function of variables? is it quadratic? $\endgroup$ – Brout Jul 31 '15 at 14:33
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$ – user6973 Jul 31 '15 at 14:41
  • $\begingroup$ This is just a linear blow up then. $\endgroup$ – Brout Jul 31 '15 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.