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