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 in, problems and/or hierarchy:
“I have a horror of people who speak about the beautiful. What is the beautiful? One must speak of problems in painting!”
—Pablo Picasso (18811973)
“The problems of the world, AIDS, cancer, nuclear war, pollution, are, finally, no more solvable than the problem of a tree which has borne fruit: the apples are overripe and they are fallingwhat can be done?... Nothing can be done, and nothing needs to be done. Something is being donethe organism is preparing to rest.”
—David Mamet (b. 1947)
“In the world of the celebrity, the hierarchy of publicity has replaced the hierarchy of descent and even of great wealth.”
—C. Wright Mills (19161962)