Please enable JavaScript.
Coggle requires JavaScript to display documents.
P and NP Problems - Coggle Diagram
P and NP Problems
Polynomial
Class P is a class of decision problems that can be solved in polynomial time by (deterministic) algorithms
-
-
-
Knapsack problem
Find the most valuable subset of n items of given positive integer weights and values that fit into a knapsack of a given positive integer capacity.
Partition problem
Given n positive integers, determine whether it is possible to partition them into two disjoint subsets with the same sum.
Bin-packing problem
Given n items whose sizes are positive rational numbers not larger than 1, put them into the smallest number of bins of size 1.
Graph-coloring problem
For a given graph, find its chromatic number, which is the smallest number of colors that need to be assigned to the graph’s vertices so that no two adjacent vertices are assigned the same color.
-
-
-
polynomially reducible
This definition immediately implies that if a problem D1 is polynomially reducible to some problem D2 that can be solved in polynomial time, then problem D1 can also be solved in polynomial time (why?).
NP- complete
The fact that closely related decision problems are polynomially reducible to
each other is not very surprising.