Complete Problems
Decision problems can be ordered according to many-one reducibility and related feasible reductions such as polynomial-time reductions. A decision problem P is said to be complete for a set of decision problems S if P is a member of S and every problem in S can be reduced to P. Complete decision problems are used in computational complexity to characterize complexity classes of decision problems. For example, the Boolean satisfiability problem is complete for the class NP of decision problems under polynomial-time reducibility.
Read more about this topic: Decision Problem
Famous quotes containing the words complete and/or problems:
“Better wear out shoes than sheets.”
—18th-century Scottish proverb, collected in J. Kelly, Complete Collection of Scottish Proverbs (1721)
“Imagination is a valuable asset in business and she has a sister, Understanding, who also serves. Together they make a splendid team and business problems dissolve and the impossible is accomplished by their ministrations.... Imagination concerning the world’s wants and the individual’s needs should be the Alpha and Omega of self-education.”
—Alice Foote MacDougall (1867–1945)