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

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?

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$$.