15
$\begingroup$

The most common way in which oracles occur in complexity theory is as follows: A fixed oracle is made available to, say, a Turing machine with certain limited resources, and one studies how the oracle increases the computational power of the machine.

There is, however, another way in which oracles sometimes occur: as part of the input. For example, suppose I want to study algorithms for computing the volume of a given high-dimensional polytope. Classically, the polytope would need to be specified by providing a list of its facets or some other explicit representation. However, we can also pose the problem of computing the volume of a polytope that is specified by a volume oracle, that takes the coordinates of a point in space as input and outputs "yes" if and only if the given point lies inside the polytope. Then we can ask what computational resources are needed to compute the volume of a polytope that is specified in this manner. In this particular case we have the very nice polynomial time approximation scheme of Dyer, Frieze, and Kannan and, interestingly from the complexity theory point of view, a proof that randomness helps in an essential way for this problem, in that no deterministic algorithm can perform as well as the Dyer-Frieze-Kannan algorithm.

Is there a systematic way to study the complexity theory of problems in which oracles are provided as part of the input? Does it somehow reduce to the usual theory of complexity classes with oracles? My guess is no, and that because there are too many different ways that an oracle could be supplied as part of the input, every problem of this sort has to be handled in an ad hoc manner. However, I would be happy to be proved wrong on this point.

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
19
$\begingroup$

It's called Type-2 Complexity Theory. There's a paper by Cook, Impagliazzo and Yamakami that ties it nicely to the theory of generic oracles.

Improve this answer
$\endgroup$
9
$\begingroup$

This must be far from a complete answer, but hopefully it points to some places to look at.

Problems where part of the input is given as an oracle are sometimes called problems with implicit input. It is a convenient model e.g. when studying probabilistically checkable proofs.

An important area of study on the problems with implicit input is the theory of query complexity, where the complexity is measured solely by the number of queries to the input oracle, ignoring the amount of computation between queries. Many complexity classes have their counterparts in query complexity, and a separation between complexity classes in query complexity often implies an oracle separation between the corresponding classes in computational complexity.

I do not know the study of complexity classes of problems with implicit input (rather than individual problems) taking the cost of computation into account, but probably some people know.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ now that you mentioned, do you know in what cases query complexity does not give an oracle separation between the corresponding classes? $\endgroup$
    – Marcos Villagra
    Oct 8, 2011 at 0:44
  • $\begingroup$ @MarcosVillagra: Not specifically, but I doubt that a query-complexity counterpart of a class in computational complexity is always well-defined. $\endgroup$
    – Tsuyoshi Ito
    Oct 8, 2011 at 13:26
5
$\begingroup$

The model where input is provided as an oracle is studied in computability theory and computable analysis. One of the models that seem close to what you want is the TTE model (Type Two Effectivity). A good reference for it is Klaus Weihrauch's book "Computable Analysis". He also briefly talks about complexity in chapter 7.

Ker-I Ko's book "Computational Complexity of Real Functions" discusses another model of access to the oracle which seem more suitable for complexity. The issues about representation of higher type objects and the method to access the oracle are delicate matters. See for example Stephen A. Cook and Akitoshi Kawamura's recent paper "Complexity Theory for Operators in Analysis" from STOC 2010 and his PhD thesis. One of the main issues is that to make the model reasonable one needs to give the machine enough time to process the answers from the oracle (otherwise one cannot even compute the application operator). For polynomial time and polynomial space it can be done using higher order polynomials based on Stephen A. Cook and Bruce M. Kapron's papers "A new characterization of type-2 feasibility" FOCS 1991 and "Characterizations of the basic feasible functionals of finite type" STOC 1989.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.