Complexity of detecting a convex body in $\mathbb{R}^n$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T23:28:16Z http://mathoverflow.net/feeds/question/80242 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80242/complexity-of-detecting-a-convex-body-in-mathbbrn Complexity of detecting a convex body in $\mathbb{R}^n$? han 2011-11-06T20:57:30Z 2011-11-07T19:14:12Z <p>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,</p> <ol> <li>$K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.</li> <li>The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, I assume that the boundary is not a hyperplane.)</li> <li>Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.</li> <li>We have two initial points $\mathbf{x},\mathbf{y}$ on hand, where $\mathbf{x}\in K_1$ and $\mathbf{y}\in K_2$.</li> </ol> <p>Essentially, $K_0$ can be viewed as a black box. Further assume that one can query any point in $K_0$ with a <em>membership oracle</em>, namely a procedure that given a point $\mathbf{p}\in K_0$, reports the set contains $\mathbf{p}$. </p> <p><strong>The goal is to determine which set is convex using membership queries.</strong></p> <p>My questions:</p> <ol> <li>Can this be done with <em>finite</em> number of queries?</li> <li>What is the complexity class of this problem?</li> </ol> <p>Thanks.</p> http://mathoverflow.net/questions/80242/complexity-of-detecting-a-convex-body-in-mathbbrn/80317#80317 Answer by Joel David Hamkins for Complexity of detecting a convex body in $\mathbb{R}^n$? Joel David Hamkins 2011-11-07T17:52:50Z 2011-11-07T19:14:12Z <p>You haven't said precisely what you mean by an algorithm here, and this is actually a nontrivial issue since your question is outside the usual finitary context of computability theory, so it isn't clear what you might mean, and there are choices to be made about it. </p> <p>One way to make the concept precise would be to work with $\mathbb{Q}^n$ rather than $\mathbb{R}^n$ (or some other countable dense set), that is, to finitize the problem by regarding all the relevant reals as rational. In this case, we can use a standard Turing machine concept of computability to make the question precise. For this manner of formalization, we regard the "input" as fixing the oracles for the $K_i$, and the question is whether there is a Turing machine program that can detect the answer correctly regardless of the oracle (subject to them satisfying your hypotheses). Let me assume first that the hypotheses are that exactly one of the $K_i$ are non-convex. </p> <p><b>Theorem.</b> With the $\mathbb{Q}^n$ formalization just described, the answer is yes, there is an algorithm.</p> <p>Proof. Consider the algorithm that systematically produces all triples $(p,q,r)$ of rational points in $\mathbb{Q}^n$, such that $q$ is on the line from $p$ to $r$, and checks membership in each $K_i$. Note that any instance of non-convexity will therefore be revealed. Thus, we will at some finite time in the algorithm, discover which of the $K_i$ is not convex, and thus produce the correct answer in finitely many steps. QED</p> <p>The previous algorithm relied on the fact that instances of non-convexity can be discovered in finitely many steps. </p> <p><b>Theorem.</b> In the $\mathbb{Q}^n$ formalization, in the context where the input sets $K_1$ and $K_2$ might <em>both</em> be convex (and in such a case only, we allow the boundary to be a hyperplane), then there is no computable procedure that will always work.</p> <p>Proof. Suppose that there were such a procedure in the case $n=1$. Let $K_0=(0,2)$, $K_1=(0,1)$ and $K_2=[1,2)$. The algorithm will halt in finitely many steps, having made queries about reals $q_0$, $q_1$, ... $q_n$, and stating that one of the sets, lets suppose $K_1$, is convex, which is true. Consider now the modification of the sets by letting $r$ be the largest $q_i$ below $2$ (or $\frac32$, whichever is larger), and using $K_1'=(0,1)\cup (r,2)$ and $K_2'=[1,r]$. Since the answers to the queries about the $q_i$ are exactly the same for this configuration as in the original problem, the algorithm will again say that $K_1'$ is convex, but in this case, it would be incorrect. QED</p> <p>Since the $K_i$ input is infinitary in nature, it isn't immediately clear what you might mean by "complexity class". However, the problem does have an inherent semi-decidable nature, since instances of non-convexity are revealed by a single instance. In the case where one side or the other must be non-convex, this semi-decidable nature becomes decidable, since we can know which is convex by discovering the other set to be non-convex. </p> <p>Let us now try to consider the general case of $\mathbb{R}^n$. We don't have a standard formal notion of computability here (there are several distinct notions of computability on the reals, such as BSS machines, computable analysis, descriptive set-theoretic notions of "computability", infinite time computability). Note that the input to the algorithm is the <em>sets</em> $K_i$, rather than a real number. </p> <p>But let's try to be flexible and allow a more generous concept of algorithm, subject to the following properties: an algorithm is a deterministic procedure that (somehow) produces points $p$ in $\mathbb{R}^n$, makes inquiries about whether they are in $K_0$, $K_1$ and $K_2$, and then uses the resulting yes/no answers to those queries to produce additional real numbers about which queries may be made. Eventually, based on the result of the queries, the algorithm is supposed to give an output by specifying whether $K_1$ or $K_2$ is convex. In particular, in this set-up, the same algorithm can be used with many different $K_0$, $K_1$ and $K_2$, and the reals produced depend only on the answers to the queries, rather than on the oracle sets themselves. We give the "input" of $K_i$ to the algorithm by attaching the black boxes, without providing any additional information about the $K_i$ sets, except that they satisfy the assumptions you identified. In this case, it doesn't matter whether one insist that exactly one or at most one $K_i$ is non-convex. </p> <p><b>Theorem.</b> With the $\mathbb{R}^n$ manner of formalization just described, there can be no algorithm correctly identifying a convex $K_i$. </p> <p>Proof. Suppose that there were such an algorithm in the case $n=1$. Call the algorithm $e$. Consider the set $Q$ of all real numbers that will ever be produced by the algorithm $e$ for a membership query for any combination of sets $K_0$, $K_1$ and $K_2$. Our assumptions on the nature of the algorithm ensure that $Q$ is a countable set, since any real produced during the course of any computation is produced as the result of a finite sequence of yes/no answers to the previous queries, and there are only countably many such possible patterns of membership. Let $r\lt s\lt t$ be real numbers not in $Q$, and consider the two possible inquiries:</p> <ul> <li>$K_0=[r,t]$, $K_1=\{r\}\cup[s,t]$, $K_2=(r,s)$. </li> <li>$K_0=[r,t]$, $K_1=[s,t)$, $K_2=[r,s)\cup\{t\}$. </li> </ul> <p>Because these two input configurations agree on $Q$, the algorithm must give the same output for both of them. But in the first case, it $K_2$ that is convex, while in the second, it is $K_1$ that is convex. So there can be no such algorithm. QED</p> http://mathoverflow.net/questions/80242/complexity-of-detecting-a-convex-body-in-mathbbrn/80319#80319 Answer by Michael Biro for Complexity of detecting a convex body in $\mathbb{R}^n$? Michael Biro 2011-11-07T17:56:25Z 2011-11-07T17:56:25Z <p>Without more constraints on the problem, there is no deterministic algorithm that can decide which is convex with a finite number of queries. For randomized algorithms, I think that you can never get a finite expected number of queries.</p> <p>Take $K_0$ to be a sphere. Run your algorithm, and let every query response be $K_1$. Now, whatever the response of the algorithm, we can construct a contradicting example with the same responses.</p> <p>If the response was $K_1$ is convex, take $K_2$ to be a small sphere in $K_0$ that is disjoint from the query set. Then, $K_2$ is convex and $K_1$ is not.</p> <p>If the response was $K_2$ is convex, we are going to take a slightly flattened sphere to be $K_1$ and the non-convex spherical cap to be $K_2$. Take the convex hull of the query points and choose a supporting hyperplane of any face of the convex hull. If we remove the spherical cap defined by the intersection of $K_0$ and the hyperplane and bulge the resulting flat face outwards, we get $K_1$ as convex and $K_2$ is not convex.</p>