Separability by piecewise testable languages is PTime-complete

Piecewise testable languages form the first level of the Straubing-Thérien hierarchy. The membership problem for this level is decidable and testing if the language of a DFA is piecewise testable is NL-complete. So far, this question has not been addressed for NFAs in the literature. We fill in this gap and show that it is PSpace-complete. The main interest of this paper is, however, the lower-bound complexity of separability of regular languages by piecewise testable languages. Two regular languages are separable by a piecewise testable language if the piecewise testable language includes one of them and is disjoint from the other. For languages represented by NFAs, separability by piecewise testable languages is decidable in PTime. We show that it is PTime-hard and that it remains PTime-hard even if the input automata are minimal DFAs. As a result, it is unlikely that separability of regular languages by piecewise testable languages can be solved in a restricted space or effectively parallelized.