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:
“Thus when I come to shape here at this table between my hands the story of my life and set it before you as a complete thing, I have to recall things gone far, gone deep, sunk into this life or that and become part of it; dreams, too, things surrounding me, and the inmates, those old half-articulate ghosts who keep up their hauntings by day and night ... shadows of people one might have been; unborn selves.”
—Virginia Woolf (1882–1941)
“The man who is forever disturbed about the condition of humanity either has no problems of his own or has refused to face them.”
—Henry Miller (1891–1980)