New answers tagged

7

The first definition you are referring to is probably the one that defines $\mathsf{NP}$ as the set of problems $\Pi$ for which there exist a non-deterministic poly-time Turing machine that decides $\Pi$. Since any problem $\Pi \in \mathsf{P}$ can be decided by a deterministic poly-time Turing machine $T$, and $T$ itself is also a non-deterministic Turing ...


0

A problem $L$ is $\text{NP}$-complete if $L$ is in $\text{NP}$, and $L$ is $\text{NP}$-hard (that is, $A\leq_p L$ for all $A\in \text{NP}$ ). Consider the following claims. Claim 1: if $L$ is $\text{NP}$-complete and $L\in \text{P}$, then $\text{NP} \subseteq \text{P}$ (that is, all problems in $\text{NP}$ can be solved in deterministic polynomial time). ...


3

Every language that is in NP is by definition decidable. Becase if a language L is in NP, than there is a nondeterministic Turing Machine that decides it in polynomial time, and thus L is decidable.


2

Each time you remove a vertex $v$ with degree $<c−1$, the degree of all its neighbours will be reduced by 1, so if any neighbor $u$ gets a degree $<c−1$ after removing $v$, remove $u$ as well; don't stop on $v$. Once you are done you will get what is called the ($c−1$)-core of the graph, which is the induced subgraph where all of its vertices has a ...


0

The problem is NP-hard, so you shouldn't expect any efficient algorithm that will always work. You can look for heuristics, or approximation algorithms, or sometimes-efficient algorithms. If I had to solve it in practice, probably the first thing I would try would be to use a SAT solver. Introduce a boolean variable $x_v$ for each vertex $v$; then add ...


1

The language $L_1$ is in P since you can brute force an optimal vertex cover in each connected component. The language $L_2$ is NP-hard by reduction from vertex cover. Roughly, given an arbitrary graph, we have to make it connected and to add another connected component, controlling the change of the minimum vertex cover throughout the process.


Top 50 recent answers are included