zbMATH — the first resource for mathematics

Expanders, randomness, or time versus space. (English) Zbl 0606.68042
Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 325-329 (1986).
[For the entire collection see Zbl 0591.00015.]
Let EH be the hypothesis that a certain type of expander graph has an explicit construction. Let io-SPACE(T(n)) be the class of problems solvable by algorithms which for infinitely many inputs use at most space t(n). Then the following holds:
There exists \(\epsilon >0\) such that for any time bound t(n), \[ EH\to (P=R \text{ or } (\text{TIME}(t(n))\cap \{1\}^*)\subseteq io- \text{SPACE}(t^{1-\epsilon}(n)). \]

68Q25 Analysis of algorithms and problem complexity