Summary: In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language \(L\) over a finite alphabet \(\Sigma \), is the set of all prefixes (resp., suffixes, factors, subwords) of all words of \(L\) equal to \(\Sigma^{\ast}\)? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černý, and Restivo’s conjecture on the minimal uncompletable word.