Tag Info

2

Yes, you are right. Having $x \leftrightarrow (x \rightarrow z)$ one can deduce that $x\equiv 1$ and $z \equiv 1$. In the paper you cite (the link is to another one btw.), rule 6 allows only to deduce that $x\equiv 1$ holds. But then you have the triplet $(1,1,z)$ and you can apply rule 4 $\frac{(x,1,z)}{x/z}$ to deduce $z\equiv x$, i.e., $z \equiv 1$ holds, ...

1

An algorithm running in time $2^n$ is extremely slow. Fortunately, there are better algorithms for solving 2SAT. Here is one such algorithm. Suppose that $C_1$ and $C_2$ are two clauses (disjunctions of variables) such that $C_1$ contains some variable $x$ and $C_2$ contains its negation $\bar{x}$. Let $C$ be the clause formed by taking the disjunction of ...

-1

3SAT is NP-complete and 2SAT is NL-complete. So 2SAT is in P.

2

Miltersen, Radhakrishnan and Wegener construct, in their paper On converting CNF to DNF, a function which has a polynomial size CNF, but whose smallest DNF has size $2^{n-\Theta(n/\log n)}$. In particular, even if the input CNF has polynomial size, you cannot expect to do better than exponential time, since the output might be that long.

5

One possibility is to take the tensor squares of the vector: replace each vector $x$ with a new vector $\hat{x}$ given by $\hat{x}_{ij} = x_i x_j$ (the vectors have length $k^2)$. We have $$\langle \hat{x}, \hat{y} \rangle = \sum_{ij} x_i x_j y_i y_j = \langle x,y \rangle^2.$$ Therefore if you know the minimum inner product, you can solve OV. It remains to ...

0

For the version where every clause must have exactly $k$ literals: There are ${n \choose k} 2^n$ possible clauses. (Why? Because you must choose exactly $k$ of the variables to appear in the clause, and then for each variable, you choose whether it appears negated or not.) A formula is obtained by choosing some subset of those possible clauses. So, the ...

1

In the Resolution proof system, at any given point in time, we have a set $S$ of clauses. If $S$ contains two clauses $\alpha \lor x$ and $\beta \lor \lnot x$, we can resolve to obtain the new clause $\alpha \lor \beta$, which we add to $S$. We do not remove the original clauses. Rather, they stay in $S$. A given collection of clauses is either satisfiable ...

4

Instead of $\mathsf{TILING}$, I proved that $\mathsf{RectangleTILING}$ is $\mathsf{NP}$-complete by finding a reduction from $\mathsf{3SAT}$. Problem $\mathsf{RectangleTILING}$: Input: a set $T$ of tiles, two dimensions $M$ and $N$ (in binary or unary, it doesn't matter); Question: is it possible to cover a rectangle of size $N\times M$ with tiles of $T$? ...

Top 50 recent answers are included