-1
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ circuit-SAT to formula-SAT $\;$ $\endgroup$
    – user6973
    Commented Jul 31, 2015 at 13:32
  • $\begingroup$ @RickyDemer Could you please write your answer? $\endgroup$
    – Turbo
    Commented Jul 31, 2015 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
    Commented Aug 3, 2015 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
    Commented Aug 3, 2015 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
    Commented Aug 3, 2015 at 13:05

1 Answer 1

Reset to default
0
$\begingroup$

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.

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

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.