Hot answers tagged

8

This problem is not in $NP$ (unless $PH$ collapses), since it is already $P^{NP}$-hard, see e.g. [1]. [1] K.W. Wagner. More Complicated Questions about Maxima and Minima, and some Closures of NP. Theoretical Computer Science, 51(1-2):53 –80, 1987. Edit: As it was pointed out in the comments, $NP$ is indeed formally defined as a collection of decision ...


8

[Now that the question's been clarified I'll post my previous comment as an answer.] It's in $\mathsf{P}$. Start with unit propagation. Afterwards, what's left on the right-hand sides will be monotone, so will be satisfied by setting all remaining variables to True. (If you want to count the number of solutions, on the other hand, that might be harder.)


7

There are several #k-SAT algorithms in the literature which can beat $2^n$. Here is a randomized one that gets $2^{n(1-1/O(k))}$ time (like PPSZ): https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf There is also a deterministic algorithm with $2^{n(1-1/O(k))}$ runtime behavior. Here is a link: http://tmc.web.engr.illinois....


6

EDIT: Strengthened Theorem 2. The answer to the problem as posed is no, unless P=NP: Theorem 1. Unless P=NP, there is no LP polytope for Horn-SAT that has only integer extreme points and is optimizable in polynomial time. On the other hand, the natural polytope $P$ given in the post still suffices to solve Horn-SAT via linear programming, as the solution to ...


5

The following paper answers the question in the affirmative – the variant remains NP-hard using a reduction from Monotone Planar 3-SAT: http://epubs.siam.org/doi/abs/10.1137/1.9781611976465.105 (arXiv: http://arxiv.org/abs/2009.12369) The paper presents a slightly more restricted variant, Monotone Planar 3-SAT with Neighboring Variable Pairs, which requires ...


4

This is an answer to the updated question (the original question seems harder). Let $\mu'_k$ be the smallest constant such that $k$-SAT that has clauses of length exactly $k$ and no trivial clauses has a $O(2^{\mu'_k m})$ time algorithm. Let $\mu_k$ be the smallest constant such that $k$-SAT with any clauses of length at most $k$ has an $O(2^{\mu_k m})$ time ...


4

For arbitrarily large number $n$ of variables, the following CNF formula $\phi$ is not satisfiable, has only three clauses, and a $2K_2$-free clause-variable incidence graph: $C_1=(x_1)$, $C_2=(\neg x_1)$, $C_3=(x_1,\ldots,x_n)$. Thus, to get more interesting lower bounds one needs to make assumption about the minimum clause size or about the size of classes ...


4

This is NP-hard. Here is a reduction from SAT. Suppose you have a CNF formula $\varphi$ with variables $x_1,\dots,x_n$. Add variables $x'_1,\dots,x'_n$ and clauses of the form $x_i \to \neg x'_i$ and $x_i \lor x'_i$. For each clause in $\varphi$, we add a corresponding $\cdots \lor \cdots$ clause: e.g., if $x_i \lor \neg x_j \lor x_k$ is a clause in $\...


2

If SAT is in polylog space then PH should also be in polylog space, since the typical complete problems work under logspace reductions. By padding this implies e.g. Sigma3EXP is in PSPACE. So yes, in this case PSPACE is not in P/poly but moreover PSPACE has functions requiring maximum circuit complexity. At any rate the algorithmic hypothesis here is a lot ...


2

In both questions the answer is the same for any exponent $1 < \alpha < 2$. For the first question, we can use a degeneracy based algorithm to find an independent set of size $\Omega(\frac{n}{n^{\alpha-1}}) = \Omega(n^{2-\alpha})$ in polynomial time. Therefore we get an FPT algorithm for every constant $\alpha$ simply by outputting YES if $k < c n^{...


2

It sounds like what you want are universal factor graphs. Such graphs exist for every NP-hard boolean CSP and in many cases are optimally inapproximable.


2

$(x< y) \land (y < z) \land (z < x)$


1

See Jan Krajicek, "A note on SAT algorithms and proof complexity", 2012 I am not sure if we have any result for random unsat instances (how do you define a random unsat instance?).


1

The core of DPLL uses essentially QSAT identity $∃xA = A[x/1] \vee A[x/0]$. When implemented with backtracking space requirements are not high. function DPLL(Φ) [...] return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)}); If you supply the negation $\neg B$ of your problem to a SAT solver, the SAT solver will decide QSAT $∀x_1..∀x_nB$ for you and act as a ...


1

Since the original question title asks for theoretical explanations, let me point to a paper that might provide a kind of non-standard theoretical explanation. The main result of the paper is that one can design a polynomial time errorless heuristic with exponentially small failure rate for all paddable languages (including SAT), if the errors are counted by ...


Only top voted, non community-wiki answers of a minimum length are eligible