0
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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\}$). $\endgroup$ – Marzio De Biasi May 5 '11 at 9:47
  • $\begingroup$ @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. $\endgroup$ – Cyker May 7 '11 at 18:03
  • $\begingroup$ ok, thank you. I was writing a comment suggesting you to look at time-bounded Kolmogorov complexity, but imz anticipated me :-) $\endgroup$ – Marzio De Biasi May 7 '11 at 23:52
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Cyker May 3 '11 at 17:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov May 3 '11 at 17:20
  • 1
    $\begingroup$ 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). $\endgroup$ – Sasho Nikolov May 3 '11 at 20:36
  • 1
    $\begingroup$ @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). $\endgroup$ – Sasho Nikolov May 8 '11 at 1:12
  • 1
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov May 8 '11 at 1:15
1
$\begingroup$

It looks similar to time-bounded Kolmogorov complexities 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.

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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: oai.cwi.nl/oai/asset/1319/1319A.pdf $\endgroup$ – Marzio De Biasi May 10 '11 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.