Please enable JavaScript.
Coggle requires JavaScript to display documents.
Polynomial time, Hamiltonian circuit problem, Nondeterministic algorithm,…
Polynomial time
Tractable
Problems that can be solved in polynomial time
P:
Class P is a class of decision problems that can be solved in
polynomial time by (deterministic) algorithms.
Undecidable
Halting Problem
Decidable
Intractable
.
Problems that cannot be solved in polynomial time
Computational complexity
Hamiltonian circuit problem
Traveling salesman problem
Find the shortest tour through n cities with known positive integer distances between them (find the shortest Hamiltonian circuit in a complete graph with positive integer weights).
Knapsack problem
Partition problem
Bin-packing problem
Graph-coloring problem
Integer linear programming problem
Find the maximum (or minimum) value of a linear function of several integer-valued variables subject to a finite set of constraints in the form of linear equalities and inequalities.
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.
Given n items whose sizes are positive rational numbers not larger than 1, put them into the smallest number of bins of size 1
Given n positive integers, determine whether it is possible to partition them into two disjoint subsets with the same sum.
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.
Determine whether a given graph has a Hamiltonian circuit—a path that starts and ends at the same vertex and passes through all the other vertices exactly once.
Nondeterministic algorithm
Is a two-stage procedure that
takes as its input an instance I of a decision problem and does the following.
Nondeterministic polynomial
Time efficiency of its verification stage is
polynomial.
M14