+1

What is NP complete? How to prove if a problem is NP complete?

11/20/2018 8:24:34 PM

Yousaf

5 Answers

New Answer

+7

A quick demystifier on P/NP/NPH/NPC problems: https://en.m.wikipedia.org/wiki/NP-hardness#NP-naming_convention

+5

"NP" is also online slang, an acronym for "No Problem", people (self included) often reply, "NP :)" when thanked. #disambiguation #lol #factoid #NP

+2

Usually the way you prove NP-completeness is to find a reduction to a problem that you already know is NP-complete (SAT, travelling salesman, ...)

0

Thank you!

0

Yes exactly. This is what Prof has written in lecture notes. HCP, TSP