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:
“The complete life, the perfect pattern, includes old age as well as youth and maturity. The beauty of the morning and the radiance of noon are good, but it would be a very silly person who drew the curtains and turned on the light in order to shut out the tranquillity of the evening. Old age has its pleasures, which, though different, are not less than the pleasures of youth.”
—W. Somerset Maugham (1874–1965)
“Our young people are diseased with the theological problems of original sin, origin of evil, predestination, and the like. These never presented a practical difficulty to any man,—never darkened across any man’s road, who did not go out of his way to seek them. These are the soul’s mumps, and measles, and whooping- coughs, and those who have not caught them cannot describe their health or prescribe a cure. A simple mind will not know these enemies.”
—Ralph Waldo Emerson (1803–1882)