We study the complexity of several fundamental problems in the testing of finite state machines (FSMl Our main results are as follows. Distinguishing sequences (State Identification): (1) We show that it is PSPACE-complete to determine whether an FSM has a preset distinguishing sequence. There are machines that have distinguishing sequences, but only of exponential length. (2) We give a polynomial time algorithm that determines whether an FSM has an adupfive distinguishing sequence. (The previous classical algorithms take exponential time.) Furthermore, if there is an adaptive distinguishing sequence, then we give an efficient algorithm that constructs such a sequence of length O (n2 ) (which is the best possible), where n is the number of states.