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:
“Although my parents have never been the kind to hint around about grandchildren, I can think of no better tribute to them than giving them some.... I can’t help thinking that the cycle is not complete until I can introduce them to a child of their child. And I can think of no better comfort when they are gone than to know that something of them lives on, not only in me but in my children.”
—Anne Cassidy. “Every Child Should Have a Father But....,” McCall’s (March 1985)
“I rarely speak about God. To God, yes. I protest against Him. I shout at Him. But to open a discourse about the qualities of God, about the problems that God imposes, theodicy, no. And yet He is there, in silence, in filigree.”
—Elie Wiesel (b. 1928)