0
$\begingroup$

I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.


How I understand polynomial reduction is that you can use it to show that:

  • Problem A is in P if:

B is in P and you can reduce A to B in polynomial time -> A $\leq_p$ B

  • Problem A is in NP if:

B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A


Then I read about certificates and this is how I understand the basic Idea/Components behind it:

  • Problem: Problem to solve
  • Certificate: possible solution
  • Certifier: Checks if the Certificate is correct

What I don't understand is:

  1. What do you want to show with solution that uses a certificate?
  2. When do you use one over the other ?
$\endgroup$
  • 1
    $\begingroup$ cs.stackexchange.com/questions/9556/… $\endgroup$ – Yuval Filmus Sep 11 at 12:23
  • $\begingroup$ @YuvalFilmus thanks! The post u linked helped me to gain some more knowledge about the topic. But I im still not sure about my initial question of when to use one over the other. So from my understanding you use polynomial reduction for Problems in P and Certificates are used to show that a Problem is in NP? $\endgroup$ – djikstra Sep 11 at 13:41
0
$\begingroup$
  • Problem A is in NP if: B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A

Not quite right. The class $P$ is a subset of $NP$ anyway, and hence A is already $NP$ if it is in $P$. The question is whether A is in P or not.

By reducing B to A in polynomial time, you prove that any polynomial solution of A is a polynomial solution of B. Assuming B is in $NP$ gives no useful information about A, since it is possible that B is in P as well (remember that $P \subseteq NP$. However, assuming (and probably that is what you meant), that B is NP-Hard, then, by reducing B to A, we prove that A is also hard for NP class, and hence unless P=NP, the problem A is not in P.

Now back to the question. What we know so far, $P \subseteq NP$. There are more classes above $NP$ like $EXP$ and under $P$ like $L$ for example. Which means, $$L \subseteq P \subseteq NP \subseteq EXP.$$ Check the link for more information about the classes. However, one characterization of problems in NP, is that they all admit a certifier, that can in polynomial time in the size of the input, say if the given instance is a yes instance. For example, for travelling salesman, which is an NP-Complete problem, the certificate is a path. You can clearly certify it, by checking if it visits all cities and each city exactly once and return to the beginning. Since $P \subseteq NP$ the same works for $P$ problems. Like shortest path. given a shortest path between two vertices, you can certify it it is a shortest path. For example, the certifier can compute a shortest path in polynomial time and compare the lengths.

Now the interesting part about certificates, is to certify if a problem admits a certificate for the negative answer. That means, given an instance and a certificate, the certifier can tell in polynomial time, if the instance is not in the language. Problems that admits such a certifier belong to the class $co-NP$. It is believed that $NP \neq co-NP$ unless $P = NP$. The class $P$ belongs to the intersection of both classes and hence we can certify both negative and positive answers in polynomial time.

Summary

  • Reducing $A$ to a polynomial problem proves that it is solvable in polynomial time.

  • Reducing an $NP$-Hard problem to $A$, proves that $A$ is NP-Hard and probably not in $P$. In this case, even if the problem is in $NP$ and hence is $NP$-complete, we can only say about $A$ that it is $NP$-hard, we still do not not if it is in $NP$.

  • A problem is in $NP$ if there is for each instance that belongs to language of the problem, a certificate, that can be certified in polynomial time in the size of the instance.

  • A problem is in $co-NP$ if there is for each instance, that odes not belong to the language of the problem, a certificate, that can be certified in polynomial time in the size of the instance.

  • The class $P$ belongs to the intersection of $P \cap co-NP$.

$\endgroup$

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.