New answers tagged


If you have a fixed number of variables, then you have a fixed number of assignments $2^{|\text{vars}|}$, so there's a polynomial time algorithm for checking all possible assignments.


Here is a counterexample to your proof method. The empty language reduces to 3SAT, yet it isn't NP-hard. If you reduce $L$ to 3SAT, then you can conclude that $L$ is in NP, that's it.


The first "approach" is the definition of a polynomial time many-one reduction. This is the type of reductions used for defining NP-hardness: a problem $B$ is NP-hard if for every problem $A$ in NP, there is a polytime many-one reduction from $A$ to $B$. The second "approach" is the definition of a computable many-one reduction, which is ...


Corollary $2$ is false. It seems that you are using the implication "$L$ is regular $\implies$ $L$ is decidable" in the wrong direction. If $A \le_m B$ and $B$ is regular, Corollary 1 only tells you that $A$ is decidable, which does not imply that $A$ is regular.


Theoretically, we don't know how hard k-SAT is; P ?= NP remains an open question. Empirically, random $k$-SAT at the critical clause/variable ratio for each $k$ seems to require exponentially more effort as the number of variables increases. As an exercise I ran glucose on thousands of random 3-SAT instances with a 4.26 clauses/variables ratio, averaged ...


If $L_1$ is decidable and $L_2$ is decidable then it is not necessarily true that $L_1 \le_m L_2$. Consider for example any $L_1$ distinct from $\emptyset$ and pick $L_2 = \emptyset$. In general, if $A$ and $B$ are languages, $A$ is decidable, and $B$ is non-trivial (i.e., distinct from $\emptyset$ and $\Sigma^*$) then $A \le_m B$ holds. The actual ...

Top 50 recent answers are included