Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,

1. $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
2. The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, I assume that the boundary is not a hyperplane.)
3. Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.
4. We have two initial points $\mathbf{x},\mathbf{y}$ on hand, where $\mathbf{x}\in K_1$ and $\mathbf{y}\in K_2$.

Essentially, $K_0$ can be viewed as a black box. Further assume that one can query any point in $K_0$ with a membership oracle, namely a procedure that given a point $\mathbf{p}\in K_0$, reports the set contains $\mathbf{p}$.

My questions:

1. Is there an algorithm that can determine which set is convex using finite number of membership queries?
2. What is the complexity class of this problem?

Thanks.

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,

1. $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
2. The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, I assume that the boundary is not a hyperplane.)
3. Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.
4. We have two initial points $\mathbf{x},\mathbf{y}$ on hand, where $\mathbf{x}\in K_1$ and $\mathbf{y}\in K_2$.

Essentially, $K_0$ can be viewed as a black box. Further assume that one can query any point in $K_0$ with a membership oracle, namely a procedure that given a point $\mathbf{p}\in K_0$, reports the set contains $\mathbf{p}$.

The goal is to determine which set is convex using membership queries.

My questions:

1. Can this be done with finite number of queries?
2. What is the complexity class of this problem?

Thanks.

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. Assume that,

1. $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
2. The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, I assume that the boundary is not a hyperplane.)
3. Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.
4. We have two initial points $\mathbf{x},\mathbf{y}$ on hand, where $\mathbf{x}\in K_1$ and $\mathbf{y}\in K_2$.

Essentially, $K_0$ can be viewed as a black box. Further assume that one can query any point in $K_0$ with a membership oracle, namely a procedure that given a point $\mathbf{p}\in K_0$, reports the set contains $\mathbf{p}$.

The goal is to determine which set is convex using as few membership queries as possible.

Is there an algorithm for doing this?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,

1. $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
2. The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, I assume that the boundary is not a hyperplane.)
3. Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.
4. We have two initial points $\mathbf{x},\mathbf{y}$ on hand, where $\mathbf{x}\in K_1$ and $\mathbf{y}\in K_2$.

Essentially, $K_0$ can be viewed as a black box. Further assume that one can query any point in $K_0$ with a membership oracle, namely a procedure that given a point $\mathbf{p}\in K_0$, reports the set contains $\mathbf{p}$.

My questions:

1. Is there an algorithm that can determine which set is convex using finite number of membership queries?
2. What is the complexity class of this problem?

Thanks.