2
$\begingroup$

Assume that P1, P2,..., Pn are all NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be reduced to PP1 in polynomial time, then PP1 can be reduced to PP2, and PP2 can be reduced to another NP problem in polynomial time. Specify the PP1 and PP2 classes with clear justification?

This was the question asked in one of my algorithms exam. I thought the answer for both the problems would be NP-hard, the logic which I thought of is that since all P1, P2, ...., Pn are NP problems and using the definition of NP-hard we can derive that PP1 is NP-Hard. After this for finding the class of PP2, since PP1 can be reduced to PP2. Therefore, we can say that PP2 is also NP-Hard.

The next bit of the question mentions about PP2 further being reducible to a NP problem but I don't feel that this information would be useful in finding the class of PP2. Let's assume the problem after reducing PP2 is some 'X' problem. This 'X' problem would be NP-Complete because it is NP-hard and NP as well.

My teacher says that PP1 is NP-Hard and PP2 is NP-Complete. According to him PP2 is NP- Complete because it is reduced to a NP problem but my doubt is how does this prove that PP2 is a NP problem. Please clarify my doubt.

$\endgroup$
7
  • $\begingroup$ It is not clear to me what "P1, P2,..., Pn" means. Is this supposed to be a finite list of problems in NP? An infinite list? All problems from NP? Please clarify your question by editing your post. Thanks! $\endgroup$
    – Discrete lizard
    Nov 4, 2021 at 18:19
  • $\begingroup$ They are all problems in NP. $\endgroup$
    – Gaurav
    Nov 5, 2021 at 3:37
  • $\begingroup$ Your reply is still ambiguous to me. Do you mean that these problems are the entire set NP? Or is this an arbitrary subset of NP? $\endgroup$
    – Discrete lizard
    Nov 5, 2021 at 8:18
  • 1
    $\begingroup$ Entire set of NP as far as I know. $\endgroup$
    – Gaurav
    Nov 5, 2021 at 8:52
  • $\begingroup$ The exam question is still unclear to me. How should I parse the if-statement in there? Is it "if all problems in NP can be reduced to PP1 in poly-time, then (PP1 can be reduced to PP2, and PP2 can be reduced to another NP problem in polynomial time. )" or "(if all problems in NP can be reduced to PP1 in poly-time, then PP1 can be reduced to PP2), and (PP2 can be reduced to another NP problem in polynomial time. )". In other words, where does the if-statement end? $\endgroup$
    – Discrete lizard
    Nov 5, 2021 at 9:56

1 Answer 1

2
$\begingroup$

Considering it as the entire set of NP as you said according to this statement: A problem X is NP-hard if every problem Y ∈NP reduces to X.

Since P1, P2,...Pn can all be reduced to PP1, PP1 is a NP Hard Problem.

Now we have a)PP1 reducible to PP2 and b)PP2 reducible to some NP problem. According to this:

A reduction from problem A to problem B is a polynomial-time algorithm that converts inputs to problem A into equivalent inputs to problem B. Equivalent means that both problem A and problem B must output the same YES or NO answer for the input and converted input.

– If B ∈ P, then A ∈ NP

– If B ∈ NP, then A ∈ NP

– If A is NP-hard, then B is NP-hard

According to a) subpart since PP1 is NP-hard PP2 is also NP-hard

According to b) since PP2 is reducible to NP problem PP2 is also a NP problem. And as found in a) and b) PP2 is both NP-hard and NP so PP2 is NP complete

I got the italicized reference text from https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec16.pdf

$\endgroup$
1
  • $\begingroup$ Thanks for your answer! $\endgroup$
    – Gaurav
    Nov 5, 2021 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.