New answers tagged np-complete
3
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.
2
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.
8
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 ...
2
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.
2
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 ...
1
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