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:
“Down these mean streets a man must go who is not himself mean, who is neither tarnished nor afraid.... He is the hero, he is everything. He must be a complete man and a common man and yet an unusual man. He must be, to use a rather weathered phrase, a man of honor, by instinct, by inevitability, without thought of it, and certainly without saying it. He must be the best man in his world and a good enough man for any world.”
—Raymond Chandler (1888–1959)
“The mother’s and father’s attitudes toward the child correspond to the child’s own needs.... Mother has the function of making him secure in life, father has the function of teaching him, guiding him to cope with those problems with which the particular society the child has been born into confronts him.”
—Erich Fromm (1900–1980)