HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is SAT in P if there are exponentially many clauses in the number of variables?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
satthenumberareexponentiallyvariablesmanythereclauses

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#2704, answer score: 12

Revisions (0)

No revisions yet.