<p>I assume $S&#39;$ is parametrized by $n$, i.e.~it is not defined only for a single $n$ but for infinitely many $n$ (otherwise statements like "polynomial time" do not make sense). If so, you are merely defining the fundamental problem of the complexity of deciding membership in a language (i.e. <strong>the</strong> problem of complexity theory). I am not sure what you mean by "uniform": if you mean that there could be a different algorithm for different $n$, then this is the usual non-uniform complexity.</p>

CC BY-SA 3.0
2011-05-03T17:07:22.330Z
Yes, $S'$ is parameterized by $n$ since $S' \subseteq S$ and $S = \{0,1\}^n$. _uniform_ means the algorithm can solve the problem correctly for many $S'$. This property is not required since for each $S'$ we just want the best deterministic algorithm for it. Do you have any idea what the subset $S'$ with the largest **indistinguishability complexity** looks like?
Cyker
CC BY-SA 3.0
2011-05-03T17:20:35.667Z
@cyker i still think that your definition of indistinguishability complexity is equivalent to the usual computational complexity of deciding membership in $S'$. so all the classical results apply. for example, $S'$ can contain the descriptions of turing machine-input pairs (under some standard encoding) such that the turing machine halts on that input. membership in this languages is of course undecidable. so that's about as high complexity as you can get.
Sasho Nikolov
CC BY-SA 3.0
2011-05-03T19:37:31.637Z
@Sasho Umm, I agree with you that this complexity is equivalent to deciding membership in $S'$. But I'm confused about the undecidable thing. Since for any $n$, there is a TM which can finish the task by compare the input with each $x \in S'$ one by one, though this may take in exponential time. To make the problem more meaningful, I think the TM should be given the list of elements in $S'$. We can model this by an oracle $O_{S'}$ such that $O_{S'}(x) = 1$ if $x \in S'$ and $O_{S'}(x) = 0$ if $x \notin S'$. Of course, the TM can choose to use it or not.
Cyker
CC BY-SA 3.0
2011-05-03T20:36:34.753Z
if you include such an oracle, then the problem becomes trivial, as the oracle solves the problem. 

about the undecidability: if $S'$ is not a part of the input then there exist sets for which membership is undecidable. consider that there are uncountably many languages and only countably many turing machines. a turing machine cannot cycle through all $x \in S'$ as you suggest because it doesn't have access to $S'$ (and if it does, the problem, again, is trivial).
Sasho Nikolov
CC BY-SA 3.0
2011-05-05T04:18:25.543Z
@Sasho You're right. The oracle makes the problem not interesting. Actually, given the non-uniformity, all knowledge about $S'$ can be built-in the finite control of $A_{S'}$ using a decision tree. So $A_{S'}$ can just use binary search bit by bit to guarantee correctness in time $O(n)$. So there must be some trade-offs between the size of the TM and the running time of the TM. I just don't know how to formulate this :(
Cyker
CC BY-SA 3.0
2011-05-08T01:12:12.737Z
@cyker this is true if your notion of non-uniformity is the following: say you want to recognize $S' = \{S'_i\}_1^\infty$, where $S'_n \subseteq \{0, 1\}^n$ (this is the parametrization I was asking you about); then $S'$ can be recognized with $f(n)$ bits of advice in time $t(n)$ if there exists a Turing machine $T$ and for every $n$ there exists a string $x$ of length at most $f(n)$ s.t. $T$ recognizes $S'_n$ in time $t(n)$ given access to $x$. What you are describing corresponds to $f(n) = O(2^n)$ and random access to $x$ (think of $x$ as the decision tree).
Sasho Nikolov
CC BY-SA 3.0
2011-05-08T01:15:21.657Z
what is more standard in complexity theory is to restrict *both* $f(n)$ and $t(n)$ to be  polynomial functions of $n$. Then you have the complexity class P/poly, which is also equivalent to the class of problems that can be recognized with polynomial size binary circuits. Pretty much any question about general circuits is wide open. Look these up, you'd find a lot of interesting info. I think this might be the approach you're looking for
Sasho Nikolov
CC BY-SA 3.0
2011-05-03T15:03:26.543Z
2011-05-03T15:03:26.543Z
Sasho Nikolov
<p>It looks similar to <a href="http://scholar.google.com/scholar?hl=en&amp;q=time-bounded+kolmogorov+complexity&amp;as_sdt=1,5&amp;as_ylo=&amp;as_vis=0" rel="nofollow">time-bounded Kolmogorov complexities</a> of your "$S'$" sets. A definition is given in, for example, M.Sipser "A complexity theoretic approach to randomness" 1983.</p>

<p>A time-bounded Kolmogorov complexity aims to capture the "trade-off" between the size of the description of a string and the time the generator/recognizer needs. It is an important detail what kind of "descriptions" you want to consider; as it is said in the paper by Sipser:</p>

<blockquote>
  <p>The intuition is that while   $K(s)$  is
  the length of the shortest program
  <em>generating</em> $s$, $KD(s)$   is the length
  of the shortest program which <em>accepts</em>
  only  $s$.  In pure Kolmogorov
  complexity these two measures differ
  by only an additive constant.   In the
  time restricted complexity they appear
  to be quite different...</p>
</blockquote>

<p>Your setting differs in that you are interested neither in--informally speaking--$K(S')$ nor in $KD(S&#39;)$ (regarding $S&#39;$ as a whole finite object represented as a string), but you want to regard $S&#39;$ as a set and measure the sizes and running times of programs that accept the elements of $S&#39;$. Your setting must be closely related to the research on time-bounded Kolmogorov complexity, but I'm not an expert in this field to tell you definitely whether it has been explored and what the results are, how the connection between your measure and the time-bounded variant of $KD(\cdot)$ can be characterized.</p>

CC BY-SA 3.0
2011-05-10T07:59:05.707Z
See for example: H. Buhrman, L. Fortnow, and S. Laplante. Resource-bounded Kolmogorov complexity revisited. SIAM J. Comput., 31(3):887{
905, 2002. ... also available online: http://oai.cwi.nl/oai/asset/1319/1319A.pdf
Marzio De Biasi
CC BY-SA 3.0
2011-05-07T23:29:55.737Z
2011-05-08T01:04:25.907Z
2011-05-08T01:04:25.907Z
imz -- Ivan Zakharyaschev
<p>Given set $S = \{0,1\}^n$, consider a subset $S&#39; \subseteq S$. By <em>determine</em> we mean there is a deterministic TM $A_{S&#39;}$ which always halts and defines a mapping $\{0,1\}^n \rightarrow {0,1}$ such that $A_{S&#39;}(x) = 1$ iff $x \in S&#39;$.</p>

<ol>
<li><p>If $S_1&#39;$ contains all even numbers in $S$, $\forall x \in S$, we can determine whether $x \in S_1&#39;$ in polynomial time.</p></li>
<li><p>If $S_2&#39;$ contains all numbers in $S$ which are smaller than $2^{n-1}$, $\forall x \in S$, we can determine whether $x \in S_2&#39;$ in polynomial time.</p></li>
<li><p>If $S_3&#39;$ contains $2^{n-1}$ randomly chosen numbers in $S$, $\forall x \in S$, intuitively, it may not be possible to determine whether $x \in S_3&#39;$ in polynomial time using a polynomial-size TM.</p></li>
</ol>

<p>Note that the set $S&#39;$ itself is not part of the input. In this way the running time of $A_{S&#39;}$ doesn't depend on the size of $S&#39;$.</p>

<p>Intuitively, the size and running time (which have some trade-off) of the most efficient TM $A_{S&#39;}$ (that can determine whether $x \in S&#39;$ correctly) can be viewed as the <strong>indistinguishability complexity</strong> (defined by me) of the subset $S&#39;$.</p>

<p>Question:</p>

<ol>
<li><p>Is there any formal theory that exactly defines this idea?</p></li>
<li><p>How to measure this trade-off between the size and the running time?</p></li>
<li><p>For $S = \{0,1\}^{n}$, what is the subset $S&#39;$ that has the largest indistinguishability complexity?</p></li>
</ol>

CC BY-SA 3.0
2011-05-05T09:47:23.030Z
Just a clarification request. First: the notation "{0,1}^n" usually stands for a binary string of length $n$, not a set; so what is S exactly? Is it a (given) fixed set of size n? Second: with "parametrized by n" do you mean that $S'$ is a family of (sub)sets? (in this case $S'$ is $S'_n$, and the algorithm $A_{S'}$ ($A_{S'_n}$) represents a function $f(x,n) \to \{0,1\}$).
Marzio De Biasi
CC BY-SA 3.0
2011-05-07T18:03:34.947Z
@Vor First: I think using $\{0,1\}^n$ to denote the set of binary strings of length $n$ is OK, since many famous books use such a notation (such as Katz & Lindell). Second: $S'$ is just one subset of $S = \{0,1\}^n$ ($n$ is fixed). The TM needn't be so powerful that it can handle cases for different $n$. So actually this is a non-uniform version. But since for each $n$ there is such a TM, the indistinguishability complexity can be defined for all $n$. The function $f(x,n) \rightarrow \{0,1\}$ you give is a uniform version. That's also an interesting question. Actually I'm interested in both.
Cyker
CC BY-SA 3.0
2011-05-07T23:52:33.790Z
ok, thank you. I was writing a comment suggesting you to look at time-bounded Kolmogorov complexity, but imz anticipated me :-)
Marzio De Biasi
<cc.complexity-theory>
Indistinguishability complexity of a subset
Cyker
# Indistinguishability complexity of a subset

(Asked by: username_0 on 2011-05-03)

Given set $S = \{0,1\}^n$, consider a subset $S' \subseteq S$. By *determine* we mean there is a deterministic TM $A\_{S'}$ which always halts and defines a mapping $\{0,1\}^n \rightarrow {0,1}$ such that $A\_{S'}(x) = 1$ iff $x \in S'$.

1. If $S\_1'$ contains all even numbers in $S$, $\forall x \in S$, we can determine whether $x \in S\_1'$ in polynomial time.
2. If $S\_2'$ contains all numbers in $S$ which are smaller than $2^{n-1}$, $\forall x \in S$, we can determine whether $x \in S\_2'$ in polynomial time.
3. If $S\_3'$ contains $2^{n-1}$ randomly chosen numbers in $S$, $\forall x \in S$, intuitively, it may not be possible to determine whether $x \in S\_3'$ in polynomial time using a polynomial-size TM.

Note that the set $S'$ itself is not part of the input. In this way the running time of $A\_{S'}$ doesn't depend on the size of $S'$.

Intuitively, the size and running time (which have some trade-off) of the most efficient TM $A\_{S'}$ (that can determine whether $x \in S'$ correctly) can be viewed as the **indistinguishability complexity** (defined by me) of the subset $S'$.

Question:

1. Is there any formal theory that exactly defines this idea?
2. How to measure this trade-off between the size and the running time?
3. For $S = \{0,1\}^{n}$, what is the subset $S'$ that has the largest indistinguishability complexity?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Just a clarification request. First: the notation "{0,1}^n" usually stands for a binary string of length $n$, not a set; so what is S exactly? Is it a (given) fixed set of size n? Second: with "parametrized by n" do you mean that $S'$ is a family of (sub)sets? (in this case $S'$ is $S'_n$, and the algorithm $A_{S'}$ ($A_{S'_n}$) represents a function $f(x,n) \to \{0,1\}$).  
> **username_0**: @Vor First: I think using $\{0,1\}^n$ to denote the set of binary strings of length $n$ is OK, since many famous books use such a notation (such as Katz & Lindell). Second: $S'$ is just one subset of $S = \{0,1\}^n$ ($n$ is fixed). The TM needn't be so powerful that it can handle cases for different $n$. So actually this is a non-uniform version. But since for each $n$ there is such a TM, the indistinguishability complexity can be defined for all $n$. The function $f(x,n) \rightarrow \{0,1\}$ you give is a uniform version. That's also an interesting question. Actually I'm interested in both.  
> **username_1**: ok, thank you. I was writing a comment suggesting you to look at time-bounded Kolmogorov complexity, but imz anticipated me :-)  

---

## 2 answers

### Answer by username_2 on 2011-05-03. Score: 1

I assume $S'$ is parametrized by $n$, i.e.~it is not defined only for a single $n$ but for infinitely many $n$ (otherwise statements like "polynomial time" do not make sense). If so, you are merely defining the fundamental problem of the complexity of deciding membership in a language (i.e. **the** problem of complexity theory). I am not sure what you mean by "uniform": if you mean that there could be a different algorithm for different $n$, then this is the usual non-uniform complexity.

> **Comments:**
> **username_0**: Yes, $S'$ is parameterized by $n$ since $S' \subseteq S$ and $S = \{0,1\}^n$. _uniform_ means the algorithm can solve the problem correctly for many $S'$. This property is not required since for each $S'$ we just want the best deterministic algorithm for it. Do you have any idea what the subset $S'$ with the largest **indistinguishability complexity** looks like?  
> **username_2**: @cyker i still think that your definition of indistinguishability complexity is equivalent to the usual computational complexity of deciding membership in $S'$. so all the classical results apply. for example, $S'$ can contain the descriptions of turing machine-input pairs (under some standard encoding) such that the turing machine halts on that input. membership in this languages is of course undecidable. so that's about as high complexity as you can get.  
> **username_0**: @Sasho Umm, I agree with you that this complexity is equivalent to deciding membership in $S'$. But I'm confused about the undecidable thing. Since for any $n$, there is a TM which can finish the task by compare the input with each $x \in S'$ one by one, though this may take in exponential time. To make the problem more meaningful, I think the TM should be given the list of elements in $S'$. We can model this by an oracle $O_{S'}$ such that $O_{S'}(x) = 1$ if $x \in S'$ and $O_{S'}(x) = 0$ if $x \notin S'$. Of course, the TM can choose to use it or not.  
> **username_2**: if you include such an oracle, then the problem becomes trivial, as the oracle solves the problem.   about the undecidability: if $S'$ is not a part of the input then there exist sets for which membership is undecidable. consider that there are uncountably many languages and only countably many turing machines. a turing machine cannot cycle through all $x \in S'$ as you suggest because it doesn't have access to $S'$ (and if it does, the problem, again, is trivial).  
> **username_0**: @Sasho You're right. The oracle makes the problem not interesting. Actually, given the non-uniformity, all knowledge about $S'$ can be built-in the finite control of $A_{S'}$ using a decision tree. So $A_{S'}$ can just use binary search bit by bit to guarantee correctness in time $O(n)$. So there must be some trade-offs between the size of the TM and the running time of the TM. I just don't know how to formulate this :(  
> **username_2**: @cyker this is true if your notion of non-uniformity is the following: say you want to recognize $S' = \{S'_i\}_1^\infty$, where $S'_n \subseteq \{0, 1\}^n$ (this is the parametrization I was asking you about); then $S'$ can be recognized with $f(n)$ bits of advice in time $t(n)$ if there exists a Turing machine $T$ and for every $n$ there exists a string $x$ of length at most $f(n)$ s.t. $T$ recognizes $S'_n$ in time $t(n)$ given access to $x$. What you are describing corresponds to $f(n) = O(2^n)$ and random access to $x$ (think of $x$ as the decision tree).  
> **username_2**: what is more standard in complexity theory is to restrict *both* $f(n)$ and $t(n)$ to be  polynomial functions of $n$. Then you have the complexity class P/poly, which is also equivalent to the class of problems that can be recognized with polynomial size binary circuits. Pretty much any question about general circuits is wide open. Look these up, you'd find a lot of interesting info. I think this might be the approach you're looking for  

---

### Answer by username_3 on 2011-05-07. Score: 1

It looks similar to [time-bounded Kolmogorov complexities](http://scholar.google.com/scholar?hl=en&q=time-bounded+kolmogorov+complexity&as_sdt=1,5&as_ylo=&as_vis=0) of your "$S'$" sets. A definition is given in, for example, M.Sipser "A complexity theoretic approach to randomness" 1983.

A time-bounded Kolmogorov complexity aims to capture the "trade-off" between the size of the description of a string and the time the generator/recognizer needs. It is an important detail what kind of "descriptions" you want to consider; as it is said in the paper by Sipser:

> The intuition is that while $K(s)$ is
> the length of the shortest program
> *generating* $s$, $KD(s)$ is the length
> of the shortest program which *accepts*
> only $s$. In pure Kolmogorov
> complexity these two measures differ
> by only an additive constant. In the
> time restricted complexity they appear
> to be quite different...

Your setting differs in that you are interested neither in--informally speaking--$K(S')$ nor in $KD(S')$ (regarding $S'$ as a whole finite object represented as a string), but you want to regard $S'$ as a set and measure the sizes and running times of programs that accept the elements of $S'$. Your setting must be closely related to the research on time-bounded Kolmogorov complexity, but I'm not an expert in this field to tell you definitely whether it has been explored and what the results are, how the connection between your measure and the time-bounded variant of $KD(\cdot)$ can be characterized.

> **Comments:**
> **username_1**: See for example: H. Buhrman, L. Fortnow, and S. Laplante. Resource-bounded Kolmogorov complexity revisited. SIAM J. Comput., 31(3):887{ 905, 2002. ... also available online: http://oai.cwi.nl/oai/asset/1319/1319A.pdf  

---

