New answers tagged sat
5
I'm not sure how to answer (1), but (2) is known to imply circuit lower bounds against NQP (non-deterministic quasi-polynomial time). This is from Cody Murray and Ryan Williams' STOC 2018 paper.
In fact, they show that these lower bounds follow from faster algorithms for what they call Gap Circuit Unsatisfiability: given a circuit $C$ on $n$ variables and ...
3
Under Karp reductions, the answer is exactly $\mathbf{NP}$: it is not hard to see that if a language is Karp-reducible to any $\mathbf{NP}$-language, then it is in $\mathbf{NP}$ too. On the other hand, all of $\mathbf{NP}$ reduces to $\mathbf{NP}$-complete languages by definition.
Under Turing reductions, the answer is the class $\mathbf{P}^\mathbf{NP}$: ...
2
Below I show that reordering is not possible in any sense, so a new hardness proof from scratch is needed.
It's not even possible to reorder just one side if you don't eliminate redundant cluases. This is because any pair of adjacent (cyclically) variables can be in a clause and that gives you very little freedom, you can only reorder them by a cyclical ...
2
The scaled down version of $\mathsf{PH}$ versus $\mathsf{PP}$ is $\mathsf{AC}^0$ versus $MAJ \circ \mathsf{AC}^0$, and we know that for the latter there is an exponential separation. Of course, this separation doesn't propagate exponentially up, but you could take this as philosophical evidence that $\mathsf{PH}$ is different enough from $\mathsf{PP}$ that ...
Top 50 recent answers are included
