Proof of np-completeness of problems
It is necessary to solve four problems on this topic, re-read a bunch of books on the topic, including Gehry and Johnson. Honestly, nothing comes to mind.
I am sure that there are a lot of smart and kind people in Habré. Help, please, with the decision to the beginning habrachelovek.
Actually the tasks themselves:
1) Prove that this task is np-complete, by reducing it to the 3-EXP problem. Task: splitting into Hamiltonian subgraphs. Condition: the oriented graph G = (V, A) is given. Question: Is it possible to split the vertices of the graph G into disjoint subsets V1, V2, ..., Vk such that each Vi contains at least 3 vertices, and all the subgraphs of the graph G induced by them would contain Hamiltonian cycles?
2) Prove that the given task is np-complete, by reducing it to the TP-3 problem. Task: Expansion of the substitution. Condition: the permutation b of the set {1,2, ..., N} and the sequence S1, S2, ..., Sm of subsets of the set {1,2, ..., N} is given. Question: Is it possible to represent the permutation b as a composition of permutations b = b1, b2, ..., bm, where for each i, 1 <= i <= m, the substitution bi leaves fixed the elements of the set {1,2, ... , N} \ Si?
')
3) Prove that this task is np-complete, by reducing it to the task TP-3. Task: optimal communication framework. (I will not give the condition, the easiest way to see it is in Gary and Johnson)
4) Prove that the given problem is np-complete, by reducing it to the VP problem. Task: the shortest common supersequence. Condition: a finite alphabet E, a finite set R of words in an alphabet E *, and a positive integer k are given. Question: Is there a word w in E * such that | w | <= k and each word x of R is a subsequence of w, i.e. w = w0x1w1x2w2 ... xkwk, where wi is from E *, and x = x1, x2, .., xk?
I am sure that there are a lot of smart and kind people in Habré. Help, please, with the decision to the beginning habrachelovek.
Actually the tasks themselves:
1) Prove that this task is np-complete, by reducing it to the 3-EXP problem. Task: splitting into Hamiltonian subgraphs. Condition: the oriented graph G = (V, A) is given. Question: Is it possible to split the vertices of the graph G into disjoint subsets V1, V2, ..., Vk such that each Vi contains at least 3 vertices, and all the subgraphs of the graph G induced by them would contain Hamiltonian cycles?
2) Prove that the given task is np-complete, by reducing it to the TP-3 problem. Task: Expansion of the substitution. Condition: the permutation b of the set {1,2, ..., N} and the sequence S1, S2, ..., Sm of subsets of the set {1,2, ..., N} is given. Question: Is it possible to represent the permutation b as a composition of permutations b = b1, b2, ..., bm, where for each i, 1 <= i <= m, the substitution bi leaves fixed the elements of the set {1,2, ... , N} \ Si?
')
3) Prove that this task is np-complete, by reducing it to the task TP-3. Task: optimal communication framework. (I will not give the condition, the easiest way to see it is in Gary and Johnson)
4) Prove that the given problem is np-complete, by reducing it to the VP problem. Task: the shortest common supersequence. Condition: a finite alphabet E, a finite set R of words in an alphabet E *, and a positive integer k are given. Question: Is there a word w in E * such that | w | <= k and each word x of R is a subsequence of w, i.e. w = w0x1w1x2w2 ... xkwk, where wi is from E *, and x = x1, x2, .., xk?
Source: https://habr.com/ru/post/9211/
All Articles