Title: Separability by Piecewise Testable Languages is PTime-Complete,
Abstract: 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. The question has
not yet been addressed for NFAs. We fill in this gap by showing that it is
PSpace-complete. The main result is then 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
known to be decidable in PTime. We show that it is PTime-hard and that it
remains PTime-hard even for minimal DFAs.