Suppose you are studying the computational complexity of a given problem X. It i

Question

Suppose you are studying the computational complexity of a given problem X. It is known that the Boolean satisfiability problem can be reduced to X in polynomial time. In addition, it is known that problem X is in class EXPTIME, as somebody have already developed an algorithm for X that is guaranteed to provide a solution in exponential time. Can it be the case that X is an NP-COMPLETE problem? Justify your answer and. if your answer is "yes," state what would you need to do to show that X is NP-COMPLETE.

Explanation / Answer

P versus NP problem is a major unsolved problem in computer science.
Informally speaking, it asks whether every problem whose solution can
be quickly verified by a computer can also be quickly solved by a computer.

The informal term quickly, used above, means the existence of an algorithm
solving the task that runs in polynomial time, such that the time to complete
the task varies as a polynomial function on the size of the input to the algorithm.
The general class of questions for which some algorithm can provide an answer in
polynomial time is called "class P" or just "P". For some questions, there is no
known way to find an answer quickly, but if one is provided with information showing
what the answer is, it is possible to verify the answer quickly.
The class of questions for which an answer can be verified in polynomial time is called NP,
which stands for "nondeterministic polynomial time."

Consider the subset sum problem, an example of a problem that is easy to verify, but whose
answer may be difficult to compute. Given a set of integers, does some nonempty subset of
them sum to 0? For instance, does a subset of the set {2, 3, 15, 14, 7, 10} add up to 0?
The answer "yes, because the subset {2, 3, 10, 15} adds up to zero" can be quickly verified
with three additions. There is no known algorithm to find such a subset in polynomial time,
but such an algorithm exists if P = NP; hence this problem is in NP but not necessarily in P.

An answer to the P = NP question would determine whether problems that can be verified in
polynomial time, like the subset-sum problem, can also be solved in polynomial time. If
it turned out that P NP, it would mean that there are problems in NP that are harder
to compute than to verify: they could not be solved in polynomial time, but the answer
could be verified in polynomial time.

Aside from being an important problem in computational theory, a proof either way would
have profound implications for mathematics, cryptography, algorithm research, artificial
intelligence, game theory, multimedia processing, philosophy, economics and many other fields.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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