Expanders, randomness, or time versus space
作者：
Highlights：
•
摘要
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 that for infinitely many inputs use at most space T(n). Then the following holds: There exists ϵ > 0 such that for any polynomial time bound T(n)=nk, EH→ (P=R or TIME(T(n))⊆sio-SPACE(T1−ε(n))).
论文关键词：
论文评审过程：Received 11 December 1986, Revised 25 June 1987, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(88)90035-9
