An observation on time-storage trade off

摘要

There are two main results proved here. The first states that a certain set SP of strings (those coding “solvable path systems”) has tape complexity (log n)2 iff every set in Download : Download full-size image (i.e., of deterministic polynomial time complexity) has tape complexity (log n)2. The second result gives evidence that SP does not have tape complexity (log n)k for any k.