(I asked this question also in Homework Help for Comp Sci and Engineering, but maybe someone in here can answer this)(adsbygoogle = window.adsbygoogle || []).push({});

Im just a little confused about the definition of an NP problem. The most common definition I hear is: a decision problem is in NP if it has a polynomial time certification. So if it is a yes or no question, there is a proof of it in polynomial time. But my question is, when proving a decision problem is in NP, do you have to assume the answer is yes and show a polytime certification exists and then assume the answer is no and show a polytime certification of that answer exists? Or do you choose either yes or no and show that a polytime certification of that answers exists?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Problems in NP

Loading...

Similar Threads for Problems |
---|

I The Halting Problem |

B Problem in Counting - Number of Passwords |

I A specific combination problem |

I A seemingly simple problem about probability |

I Extension of Turing computable |

**Physics Forums | Science Articles, Homework Help, Discussion**