Space-bounded reducibility among combinatorial problems

摘要

Reducibility and completeness among combinatorial problems can be formulated in terms of space bounds, in some cases refining the polynomial time-reducibility of Cook and Karp. Two versions are defined, by means of Turing machines and by bounded-quantifier formulas. Following are the main results. (1) The problem “Is there a path between specified nodes of a digraph?” is shown to be complete for the sets acceptable in nondeterministic log(·) space; (2) The problem “Given a finite function f: {1,…,n}→{1,…,n}, is there a k such that fk(1)=n?” is similarly complete for deterministic log(·) space; and (3) Each of the problems “Is T(M)=ø?” and “Is T(M) infinite?” (for M a deterministic finite automaton) is shown to be complete for nondeterministic (deterministic) log n space in the case in which the alphabet of M is arbitrary (consists of one letter).