# distinguishments between query complexity of membership oracles and standard time complexity

Many combinatorial optimization problems can be described as follows. We are given a set system $$(E,I)$$, where $$I \subseteq 2^E$$ and a weight function $$w: E \rightarrow \mathbb{N}$$. The goal is to find a member of the set system $$S \in I$$ with maximum total weight $$w(S) = \sum_{e \in S} w(e)$$. Examples include maximum independent set of a matroid and maximum matching in a graph.

In some cases, the representation of $$I$$ in the set system is via a membership oracle that determines if some $$S \subseteq E$$ is in $$I$$ in a single query. This is useful for describing set systems that require exponential size in $$E$$ to represent $$I$$.

Question: Are there set systems $$(E,I)$$ that satisfy:

(1) Finding $$S \in I$$ of maximum weight $$w(S)$$ where $$I$$ can be accessed only via a membership oracle cannot be computed in $$|E|^{O(1)}$$ queries and $$|E|^{O(1)}$$ other basic operations.

(2) I f we are given a concrete input (with no oracle), such that deciding if some $$S \subseteq E$$ belongs to $$I$$ takes $$|E|^{O(1)}$$ time, then the problem is solvable in time $$|E|^{O(1)}$$. Note that sometimes $$I$$ can be efficiently encoded and the encoding size of $$I$$ can be much smaller than the cardinality of $$I$$. For example, if $$(E,I)$$ describes a matching set system, where $$E$$ are the edges of a graph $$G = (V,E)$$ and $$I$$ are all matchings of the graph it suffices to encode only $$G$$ to solve the problem.

If $$(E, I)$$ is a matroid then (1) is solvable in time $$|E|^{O(1)}$$, and therefore this does not answer my question. Can someone provide a reference or describe a simple set system that satisfies both (1) and (2)? what if $$(E,I)$$ describes a matching set system? In this case, (2) can be computed in polynomial time but I am not sure about (1).

• Does the family of singleton set systems (i.e., $|I| = 1$) work? It is hard to find the unique element of $I$ using oracle access, but trivial if $I$ is given explicitly. Nov 11 at 16:56
• In (2) I do not necessarily mean that the encoding is explicit. I can encode the set system $(E,I)$ such that $I = \{S\}$ where $S \subseteq E$ is the single solution for some NP-Hard problem. Hence, finding $I$ is NP-Hard right?
– John
Nov 13 at 17:05