# P/NP - Polynomial Reduction vs Certificate

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 ?
• cs.stackexchange.com/questions/9556/… – Yuval Filmus Sep 11 '19 at 12:23
• @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? – djikstra Sep 11 '19 at 13:41

• 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.

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”.