  Consider the standard hospitals/residents problem, or the two-sided
many-to-one stable matching problem, and assume that the true preference lists
of both sides are complete and strict. The lists actually submitted, however,
are truncated. Let I be such a truncated instance. When we apply the
resident-proposing deferred acceptance algorithm of Gale and Shapley to I, the
algorithm produces a set of tentative matches (resident-hospital pairs). We say
that a tentative match in this set is finalizable in I if it is in the
resident-optimal stable matching for every completion of I (a complete instance
of which I is a truncation). We study the problem we call FTM (Finalizability
of Tentative Matches) of deciding if a given tentative match is finalizable in
a given truncated instance. We first show that FTM is coNP-complete, even in
the stable marriage case where the quota of each hospital is restricted to be
1.
  We then introduce and study a special case: we say that a truncated instance
is resident-minimal, if further truncation of the preference lists of the
residents inevitably changes the set of tentative matches. Resident-minimal
instances are not only practically motivated but also useful in natural
backtrack computations for the general case. We give a computationally useful
characterization of negative instances of FTM in this special case, which, for
instance, can be used to formulate an integer program for FTM. For the stable
marriage case, in particular, this characterization yields a polynomial time
algorithm to solve FTM for resident-minimal instances. On the other hand, we
show that FTM remains coNP-complete for resident-minimal instances, if the
maximum quota of the hospitals is 2 or larger.
  We also give a polynomial-time decidable sufficient condition for a tentative
match to be finalizable in the general case.
