Frontiers in Computer Science (Apr 2022)
Uniform Polylogarithmic Space Completeness
Abstract
It is well-known that polylogarithmic space (PolyL for short) does not have complete problems under logarithmic space many-one reductions. Thus, we propose an alternative notion of completeness inspired by the concept of uniformity studied in circuit complexity theory. We then prove the existence of a uniformly complete problem for PolyL under this new notion. Moreover, we provide evidence that uniformly complete problems can help us to understand the still unclear relationship between complexity classes such as PolyL and polynomial time.
Keywords
