Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-103 | 5th July 2006 00:00

Space Complexity vs. Query Complexity


Authors: Oded Lachish, Ilan Newman, Asaf Shapira
Publication: 25th August 2006 12:38
Downloads: 1127


Combinatorial property testing deals with the following relaxation
of decision problems: Given a fixed property and an input $x$, one
wants to decide whether $x$ satisfies the property or is ``far''
from satisfying it. The main focus of property testing is in
identifying large families of properties that can be tested with a
certain number of queries to the input. Unfortunately, there are
nearly no general results connecting standard complexity measures of
languages with the hardness of testing them. In this paper we study
the relation between the space complexity of a language and its
query complexity. Our main result is that for any space complexity
$s(n)\leq \log{n}$ there is a language with space complexity
$O(s(n))$ and query complexity $2^{\Omega(s(n))}$.
We conjecture that this exponential lower bound is best possible,
namely that the query complexity of a languages is at most exponential
in its space complexity.

Our result has implications with respect to testing languages
accepted by certain restricted machines. Alon et al. [FOCS 1999]
have shown that any regular language is testable with a constant
number of queries. It is well known that any language in space
$o(\log \log n)$ is regular, thus implying that such languages can
be so tested. It was previously known that there are languages in
space $O(\log n)$ which are not testable with a constant number of
queries and Newman [FOCS 2000] raised the question of closing the
exponential gap between these two results. A special case of our
main result resolves this problem as it implies that there is a
language in space $O(\log \log n)$ that is not testable with a
constant number of queries, thus showing that the $o(\log \log n)$
bound is best possible. It was also previously known that the class
of testable properties cannot be extended to all context-free
languages. We further show that one cannot even extend the family of
testable languages to the class of languages accepted by single
counter machines which is perhaps the weakest (uniform)
computational model that is strictly stronger than finite automata.

ISSN 1433-8092 | Imprint