# Generalizations of Opt P to the Polynomial Hierarchy

@article{Krentel1992GeneralizationsOO, title={Generalizations of Opt P to the Polynomial Hierarchy}, author={M. Krentel}, journal={Theor. Comput. Sci.}, year={1992}, volume={97}, pages={183-198} }

Abstract The author defined Opt P as a generalization of NP by considering problems as functions that compute their optimal value. An Opt P function is computed by applying the max (or min) operator to the branches of a nondeterministic machine. In this paper, we show that Opt P has a natural extension to the polynomial hierarchy by considering alternating Turing machines with the max and min operators. We show an equivalence between k alternations of max and min and functions computable with… Expand

#### Topics from this paper

#### 53 Citations

The Polynomial Time Function Hierarchy

- Mathematics
- 1994

We study Krentel's polynomial time function hierarchy (PFH) which classiies and characterizes optimization functions using deterministic oracle transducers and NP sets as oracles. We introduce a… Expand

The Operators min and max on the Polynomial Hierarchy

- Mathematics, Computer Science
- Int. J. Found. Comput. Sci.
- 2000

It turns out that a general max and a general min operator for complexity classes yield a refinement of Krentel's hierarchy of optimization functions, and it is proved that this refinement is strict unless the polynomial hierarchy collapses and show that the refinement is useful to exactly classify optimization functions. Expand

NP trees and Carnap's modal logic

- Mathematics, Computer Science
- Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
- 1993

This work considers problems and complexity classes definable by interdependent queries to an oracle in NP, and shows that the following problems are all P/sup NP/[O(logn)] complete: validity-checking of formulas in Carnap's modal logic, checking whether a formula is almost surely valid over finite structures in modal logics K, T, and S4, and checkingWhether a formula belongs to the stable set of beliefs generated by a propositional theory. Expand

The Operators min and max on the Polynomial Hierarchy

- Computer Science, Mathematics
- STACS
- 1997

This work defines a general maximization operator max and a general minimization operator min for complexity classes and shows that there are other interesting optimization classes beside OptP and is able to characterize the polynomial hierarchy uniformly by three operators. Expand

Uniform Characterizations of Complexity Classes of Functions

- Computer Science, Mathematics
- Int. J. Found. Comput. Sci.
- 2000

A reducibility notion between evaluation schemes leads to a necessary and sufficient criterion for relativizable inclusion between function classes, which is easily applicable and gets as a consequence, e.g., that there is an oracle A, such that min·PA⊈#·NPA (note that no structural consequences are known to follow from the corresponding positive inclusion). Expand

Uniformly Defining Complexity Classes of Functions

- Mathematics, Computer Science
- STACS
- 1998

A reducibility notion between such families leads to a necessary and sufficient criterion for relativizable inclusion between function classes, which is easily applicable and gets as a consequence e.g. that there are oracles A, B, such that min.PA \(\nsubseteq\) #·NPA, and max.NPB c#·coNPB are known to follow from the corresponding positive inclusions. Expand

Relativizing Function Classes

- Computer Science
- J. Univers. Comput. Sci.
- 2003

The strongest results, proved in the paper, are the constructions of oracles D and E, such that min·coNP D ⊆ #·P D ∧ NP DoNP D and UP E =N P E ∧ min·P E � #· P E. Expand

NP trees and Carnap's modal logic

- Mathematics, Computer Science
- JACM
- 1995

This paper studies problems and complexity classes definable by interdependent queries to an oracle in NP, and shows that the following problems are complete: validity-checking of formulas in Carnap's modal logic, checking whether a formula is almost surely valid over finite structures in modal logics K, T, and S4, and checkingWhether a formula belongs to the stable set of beliefs generated by a propositional theory. Expand

On Cluster Machines and Function Classes

- Mathematics
- 2007

We consider a special kind of non-deterministic Turing machines. Cluster machines are distinguished by a neighbourhood relationship between accepting paths. Based on a formalization using equivalence… Expand

Complements of multivalued functions

- Mathematics, Computer Science
- Proceedings of Computational Complexity (Formerly Structure in Complexity Theory)
- 1996

It is shown that computing maximum satisfying assignments can be done in coN PMV, which leads to a comparison of NPMV and coNPMV with Krentel's classes Max P and Min P and a functional analogue of Chang and Kadin's relationship between a collapse of the Boolean hierarchy over NP and a collapse the polynomial time hierarchy. Expand

#### References

SHOWING 1-10 OF 13 REFERENCES

The Complexity of Optimization Problems

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1988

It is shown that TRAVELING SALESPERSON and KNAPSACK are complete for OptP, and that CLIQUE and COLORING arecomplete for a subclass of OptP . Expand

The Polynomial-Time Hierarchy

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1976

The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established. Expand

On the Complexity of Some Two-Person Perfect-Information Games

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1978

Abstract We present a number of two-person games, based on simple combinatorial ideas, for which the problem of deciding whether the first player can win is complete in polynomial space. This… Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand

NP is as easy as detecting unique solutions

- Mathematics
- 1986

Abstract For every known NP-complete problem, the number of solutions of its instances varies over a large range, from zero to exponentially many. It is therefore natural to ask if the inherent… Expand

Simple Local Search Problems That are Hard to Solve

- Mathematics, Computer Science
- SIAM J. Comput.
- 1991

It is shown here that several natural, simple local search problems are PLS-complete, and thus just as hard. Expand

An efficient approximation scheme for the one-dimensional bin-packing problem

- Mathematics, Computer Science
- 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)
- 1982

It is proved that the LP relaxation of bin packing, which was solved efficiently in practice by Gilmore and Gomory, has membership in P, despite the fact that it has an astronomically large number of variables. Expand

How easy is local search?

- Computer Science, Mathematics
- 26th Annual Symposium on Foundations of Computer Science (sfcs 1985)
- 1985

A natural class PLS is defined consisting essentially of those local search problems for which local optimality can be verified in polynomial time, and it is shown that there are complete problems for this class. Expand

On Restricting the Access to an NP-Oracle

- Computer Science
- ICALP
- 1988

Polynomial time machines having restricted access to an NP oracle are investigated, finding that the class PNP[O(log n)] can be characterized in very different ways. Expand

The Complexity of Computing the Permanent

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1979

Abstract It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related… Expand