+ 1

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

20th Nov 2018, 8:24 PM
Yousaf
Yousaf - avatar
5 odpowiedzi
+ 7
A quick demystifier on P/NP/NPH/NPC problems: https://en.m.wikipedia.org/wiki/NP-hardness#NP-naming_convention
20th Nov 2018, 9:13 PM
Kuba Siekierzyński
Kuba Siekierzyński - avatar
+ 5
"NP" is also online slang, an acronym for "No Problem", people (self included) often reply, "NP :)" when thanked. #disambiguation #lol #factoid #NP
20th Nov 2018, 11:06 PM
non
+ 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, ...)
21st Nov 2018, 12:20 AM
Schindlabua
Schindlabua - avatar
0
Thank you!
20th Nov 2018, 9:32 PM
Yousaf
Yousaf - avatar
0
Yes exactly. This is what Prof has written in lecture notes. HCP, TSP
21st Nov 2018, 8:02 AM
Yousaf
Yousaf - avatar