How to define the languages of the implicit set system problems?

Question

There are implicit versions of some set system problems or matroid problems.

A set system is a pair $(U, \mathcal{F})$, where $U$ is a universe of size $n$ and $\mathcal{F}$ is a collection of susbets of $U$. $\mathcal{F}$ may satisfy some properties (e.g. Matroid). We define $\Phi$ is a polynomial-time oralce which determines whether $S \subseteq \mathcal{F}$ given the universe $U$ and a subset $S \subseteq U$.

We formally define the implicit set system problems: Given a universe $U$, the goal is to determine whether there exists a set $X$ satisfying the property $P$.

For example of the property $P$.

1. The size of $X \in \mathcal{F}$ at least $k$.
2. $X$ hits all the elements $S \in \mathcal{F}$.

So the size of the instance is $|U| = n$.

What is the language of the implicit problem? It seems that the input contains an oracle. How can I know the complexity of this kind of problems.

I think the size of this problem can be smaller (that is $O(\log n)$), because the input can just be a natural number, right?

Answer 1

There are different notions of complexity used for various computational problems, not all tasks fit naturally to the standard model of decision/search problems. The "classic" analysis of complexity talks about how many resources we need to compute $f(x)$ given $x$, but this misses a lot of interesting questions we can ask. Consider communication complexity, where we want to compute $f(x,y)$ where one sides holds $x$ and the other holds $y$, while minimizing the number of bits exchanged between the parties. This requires a new definition of complexity. Same goes for query complexity, where we are given a black box access to some function $f$ and we want to know how many evaluations of $f$ are required to determine if it satisfies some property $P$.

The seemingly natural way (this of course depends on the context) to determine hardness of set system problems would be in terms of standard complexity and the number of queries to the membership oracle. As the set system is given, I don't want to involve hardness of deciding whether some set is in the system, so I'll only charge one operation for querying the membership oracle. This allows, in a sense, to isolate the hardness of evaluating the property from the hardness of the system's description.