<p>Many combinatorial optimization problems can be described as follows. We are given a set system <span class="math-container">$(E,I)$</span>, where <span class="math-container">$I \subseteq 2^E$</span> and a weight function <span class="math-container">$w: E \rightarrow \mathbb{N}$</span>. The goal is to find a member of the set system <span class="math-container">$S \in I$</span> with maximum total weight <span class="math-container">$w(S) = \sum_{e \in S} w(e)$</span>. Examples include maximum independent set of a matroid and maximum matching in a graph.</p>
<p>In some cases, the representation of <span class="math-container">$I$</span> in the set system is via a membership oracle that determines if some <span class="math-container">$S \subseteq E$</span> is in <span class="math-container">$I$</span> in a single query. This is useful for describing set systems that require exponential size in <span class="math-container">$E$</span> to represent <span class="math-container">$I$</span>.</p>
<p><strong>Question:</strong> Are there set systems <span class="math-container">$(E,I)$</span> that satisfy:</p>
<p>(1) Finding <span class="math-container">$S \in I$</span> of maximum weight <span class="math-container">$w(S)$</span> where <span class="math-container">$I$</span> can be accessed only via a membership oracle cannot be computed in <span class="math-container">$|E|^{O(1)}$</span> queries and <span class="math-container">$|E|^{O(1)}$</span> other basic operations.</p>
<p>(2) I
f we are given a concrete input (with no oracle), such that deciding if some <span class="math-container">$S \subseteq E$</span> belongs to <span class="math-container">$I$</span> takes <span class="math-container">$|E|^{O(1)}$</span> time, then the problem is solvable in time <span class="math-container">$|E|^{O(1)}$</span>. Note that sometimes <span class="math-container">$I$</span> can be efficiently encoded and the encoding size of <span class="math-container">$I$</span> can be much smaller than the cardinality of <span class="math-container">$I$</span>. For example, if <span class="math-container">$(E,I)$</span> describes a matching set system, where <span class="math-container">$E$</span> are the edges of a graph <span class="math-container">$G = (V,E)$</span> and <span class="math-container">$I$</span> are all matchings of the graph it suffices to encode only <span class="math-container">$G$</span> to solve the problem.</p>
<p>If <span class="math-container">$(E, I)$</span> is a matroid then (1) is solvable in time <span class="math-container">$|E|^{O(1)}$</span>, 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 <span class="math-container">$(E,I)$</span> describes a matching set system? In this case, (2) can be computed in polynomial time but I am not sure about (1).</p>

CC BY-SA 4.0
2023-11-11T16:56:03.747Z
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.
Yuval Filmus
CC BY-SA 4.0
2023-11-13T17:05:57.880Z
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
<polynomial-time><oracles><matching><query-complexity><matroids>
distinguishments between query complexity of membership oracles and standard time complexity
John
# distinguishments between query complexity of membership oracles and standard time complexity

(Asked by: username_0 on 2023-11-05)

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

**Tags:** polynomial-time, oracles, matching, query-complexity, matroids
> **Comments:**
> **username_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.  
> **username_0**: 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?  

---

## 0 answers

