  The question whether P equals NP revolves around the discrepancy between
active production and mere verification by Turing machines. In this paper, we
examine the analogous problem for finite transducers and automata. Every
nondeterministic finite transducer defines a binary relation associating each
input word with all output words that the transducer can successfully produce
on the given input. Finite-valued transducers are those for which there is a
finite upper bound on the number of output words that the relation associates
with every input word. We characterize finite-valued, functional, and
unambiguous nondeterministic transducers whose relations can be verified by a
deterministic two-tape automaton, show how to construct such an automaton if
one exists, and prove the undecidability of the criterion.
