1
$\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
1
$\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 \mathit{NP} \subseteq \mathit{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$
0
$\begingroup$

Polynomial reduction and certificates have very little to do with each other.

Basically, we defined the set P of all easy problems that can be solved by a computer in polynomial time.

Then obviously problems not in P are hard.

We then defined the set NP of all problems which can be solved in polynomial time by a non-deterministic computer, in other words a computer that can follow an unlimited number of paths in parallel, or equivalent a computer that can make unfailingly lucky guesses, or equivalent, a computer that is given a problem and a correct hint at the solution, also known as “certificate”.

$\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.