Determine whether the following problem is NP-complete. Given several sequences

Question

Determine whether the following problem is NP-complete. Given several sequences of uppercase and lowercase letters, is it possible to select a letter from each sequence without selecting both the upper- and lowercase versions of any letter? For example, if the sequences are Abc, BC, aB, and ac, it is possible to choose A from the first sequence, B from the second and third, and c from the fourth. An example where there is no way to make the required selections is given by the four sequences AB, Ab, aB, and ab.

Explanation / Answer

the satisfiability problem is clearly in NP,since it is easy to check that whether a proposed selection of letters satisfies the conditions of the problem.cook provided that if the satisfiablity problem is solvable in polynomial time,then every problem in NP is solvable in polynomial time so that P-NP.thus we see that this seemingly bizzare and inconsequential problem is an archetypal combinatorial problem.it holds the key to the efficient solutions of all problems in NP.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.