Indistinguishability complexity of a subset Given set $S = \{0,1\}^n$, consider a subset $S&#39; \subseteq S$. By determine 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;$.


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


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;$.

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 indistinguishability complexity (defined by me) of the subset $S&#39;$.

Question:


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