New answers tagged polynomial-time
1
Saying that $D$ could be in $P$ does not disprove "$D$ is $\mathsf{NP}$-complete" since it could be the case that $\mathsf{P}=\mathsf{NP}$.
However the claim is false regardless of the $\mathsf{P}$ vs $\mathsf{NP}$ matter. Simply pick $D=\emptyset$ and $A$ as any $\mathsf{NP}$-complete problem. Clearly $D$ cannot be $\mathsf{NP}$-complete since ...
2
This is an open problem
In a paper from 2020, Maximum Clique in Disk-Like Intersection Graphs by Édouard Bonnet, Nicolas Grelier, and Tillmann Miltzow, the authors note in the abstract that
(...) The main open question (...) is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NP-hard.
and proceed to present their ...
1
As long as possible, add edges to $G$ which do not increase the chromatic number. You should get a complete multipartite graph which corresponds to an optimal coloring.
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.
1
No. However, its true that $L_2$ is at least as hard as $L_1$. The opposite isn't true: take for example $L_2$ being the halting problem, and $L_1=\emptyset$.
Top 50 recent answers are included