8
$\begingroup$

I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$.

I'd like to know why $\text{Long-SAT} \in P$. First I thought it is $\text{NPC}$ since I can do a polynomial-time reduction from $\text{SAT}$ to $\text{Long-SAT}$, no?

But maybe I can reduce $\text{2-SAT}$ to $\text{Long-SAT}$? How do I do that?

Improve this question
$\endgroup$
2
  • $\begingroup$ @Numerator: Watch out in the last sentence in the question. Reducing an easy problem (2-SAT in this case) to your problem does not mean that your problem is easy. $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 13, 2012 at 0:02
  • 1
    $\begingroup$ @TsuyoshiIto: We try to keep on top of weird tags. Please feel free to edit the occasional occurrence. If you spot wide-spread (mis)use or meet opposition, please take it to meta (rather than discussing in the comments below a question). $\endgroup$
    – Raphael
    Commented Jul 21, 2012 at 19:09

2 Answers 2

Reset to default
12
$\begingroup$

Unless I'm missing something, it's trivially in P as the length of the formula is exponential in the number of variables. Hence all $2^{n}$ truth assignments can be generated and checked in polynomial time in the length of the formula.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But a $2^n$ checks is still defined as plynoimal time? $\endgroup$
    – Numerator
    Commented Jul 12, 2012 at 10:09
  • 5
    $\begingroup$ Remember that to be in P you want an algorithm that runs in polynomial time in the size of the input. In this case, if we denote the size of the input as N we know that $\text{#clauses } \leq N$. Hence we also have $n=O(log N)$ so the $2^n$ assignments only amount to a polynomial in the overall input size $N$. Don't let texts trick you when they use the variable $n$, it's just a variable, not a special magic number that is always the best measure for the size of the input. Sorry about the formatting, I'm typing this on my phone. $\endgroup$
    – Luke Mathieson
    Commented Jul 12, 2012 at 11:37
  • $\begingroup$ @Numerator: you are doing $2^{\log n}=n$ checks, where $n$ is the length of the input. $\endgroup$
    – Xodarap
    Commented Jul 21, 2012 at 19:05
7
$\begingroup$

In this case, the answer is trivial as Luke points out. However, as you seem to have come up with the definition yourself, note this.

For SAT, so-called phase transitions regarding the ratio of variable count to clause count have been observed [1,2]. If it is small, instances are easy, and hard if it is large. There seems to be a more or less sharp transition from easy to hard. This seems to be an active area of research. cstheory.SE has some more on this phenomenon.

So, if you adjust your definition of "long" to polynomial blowup, you might indeed get an non-trivially easy class -- that is, in P -- just because you have much more clauses than variables.

  1. The SAT Phase Transition by I. P. Gent (1994)
  2. Determining computational complexity from characteristic 'phase transitions' by R. Monasson, R. Zecchina et al. (1999)
Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Actually, it's not an easy-hard but rather easy-hard-easy the pattern regarding the phase transition. There are 2 regions: underconstrained and overconstrained. In the first one, solutions are densely distributed, so you succeed quickly. In the second one you fail quickly: any reasonable algorithm finds a solution if such exists (a strong basin of attraction), and if there's no solution a backtracking algorithm can establish that quickly since potential solution paths are cut off early. Hard problems are on the boundary of these regions: the probability of a solution is low but non-negligible. $\endgroup$
    – Juho
    Commented Jul 21, 2012 at 22:45

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.