# Tag Info

### Is Monotone Not-Exactly-1 3SAT solvable in polynomial time?

Monotone Not-Exactly-1 3SAT problem (MNE1 3-SAT) This problem involves determining whether a Boolean formula in CNF, where each clause contains exactly three positive literals (no negations), can be ...
Accepted

### Why can't we prove SAT is NP complete just using the Tseytin Transformation?

NP-complete is defined with respect to Turing machines, not circuits. NP-complete specified in terms of polynomial-time algorithms, where polynomial-time algorithms are formalized as Turing machines ...
• 163k
1 vote
Accepted

I am not sure what you meant by permutations (the clauses are part of the input formula). So I will formulate the problem more precisely: Let $\varphi = C_1 \wedge C_2 \wedge \cdots \wedge C_m$ be a $\... • 3,812 0 votes ### Is such variant of SAT always satisfiable? Suppose we have a boolean formula containing multiple occurences of a pair$\{x_i,x_j\}$. Then we can eliminate repeating occurences of this pair by replacing every instance of$x_i\lor x_j$with$y\$ ...
• 1,901

Top 50 recent answers are included