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:
“We are such lovers of self-reliance, that we excuse in a man many sins, if he will show us a complete satisfaction in his position, which asks no leave to be, of mine, or any man’s good opinion.”
—Ralph Waldo Emerson (1803–1882)
“Currently, U.S. society has been encouraged by its political and subsidized mass-media intelligentsia to view U.S. life as a continual “morning in America” paradise, where the only social problems occur in the inner cities. Psychologists call this denial.”
—Ishmael Reed (b. 1938)