P-NP Problems

Question 1

P class of computational problems:

Any computational problem that can be solved in polynomial time (or better, of course) is considered a member of P

Answer 1

Given a computational problem, if there exists a polynomial time algorithm that solves the problem—where we would need to formally prove that the algorithm does indeed always provide an optimal solution to the problem—we would classify the problem as class P.

Question 2

Direction for showing P = NP

Design a poly-time algorithm for every problem in NP

what are all the problems in NP? this could take a long time

start with the most computationally-difficult problem

Answer 2

hard problems

problem X is NP-hard⇐⇒
poly-time algorithm forX=⇒poly-time algorithm∀Y∈NP

( ⇒P = NP)

Question 3

If P != NP then use “venn diagram”-like image to understand set/relationship of sets

P is a subset of NP
NP only intersects with NP-Hard. NP is not a complete subset of NP-Hard.
NP-Hard is a set intersects with NP, and the subset/region that NP and NP-Hard intersect is called NP-Complete

Answer 3

NP problems might fall into NP-Hard. The hardest NP problems are NP-complete

Just because there are solutions in NP that solve NP-Hard problems that doesn’t guarantee it can solve the hardest of NP-Hards problems

None of the solutions in P will work for NP-Complete and NP-Hard