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 chooseAfrom 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. [Kar86]

Explanation / Answer

A problem is said to be NP complete if it is a NP-hard problem and belongs to set NP.

First look at the following properties of the above problem:

Thus, the given problem is in NP.

Now let's look at whether it is in NP hard or not. NP hard problems are those for which it is not possible to prove whether polynomial solution exists or not. In the given problem, we have to check all combinations to find the solution. One method is the following:

Since, there is no polynomial algorithm that we have found out yet, so it is in NP hard category.

It is in both NP and NP-hard category, therefore, it is said to be NP-complete problem.

(NP complete is the subset of NP and NP hard problems)

If helpful, do give a thumbs up.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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