Problems in The Polynomial Hierarchy
- An example of a natural problem in is circuit minimization: given a number k and a circuit A computing a Boolean function f, determine if there is a circuit with at most k gates that computes the same function f. Let be the set of all boolean circuits. The language
- A complete problem for is satisfiability for quantified Boolean formulas with k alternations of quantifiers (abbreviated QBFk or QSATk). This is the version of the boolean satisfiability problem for . In this problem, we are given a Boolean formula f with variables partitioned into k sets X1, ..., Xk. We have to determine if it is true that
Read more about this topic: Polynomial Hierarchy
Famous quotes containing the words problems and/or hierarchy:
“I respect guilt. It is a dangerous but sometimes useful beast. The guilt that made me want to solve all my childrens problems meant trouble. The guilt that made me question my role in our mother-daughter squabbles proved helpful. Yes, I care about my kids problems, and I long to make suggestions. But these days I wait for children to ask for help, and I give it sparingly. Some things cant be fixed, and I tell them so.”
—Susan Ferraro (20th century)
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (19191990)