  A discrete function of $n$ variables is a mapping $g : X_1 \times \ldots
\times X_n \rightarrow A$, where $X_1, \ldots, X_n$, and $A$ are arbitrary
finite sets. Function $g$ is called {\em separable} if there exist $n$
functions $g_i : X_i \rightarrow A$ for $i = 1, \ldots, n$, such that for every
input $x_1, \ldots ,x_n$ the function $g(x_1, \ldots, x_n)$ takes one of the
values $g_1(x_1), \ldots ,g_n(x_n)$. Given a discrete function $g$, it is an
interesting problem to ask whether $g$ is separable or not. Although this seems
to be a very basic problem concerning discrete functions, the complexity of
recognition of separable discrete functions of $n$ variables is known only for
$n=2$. In this paper we will show that a slightly more general recognition
problem, when $g$ is not fully but only partially defined, is NP-complete for
$n \geq 3$. We will then use this result to show that the recognition of fully
defined separable discrete functions is NP-complete for $n \geq 4$.
  The case $n = 2$ is well-studied in the context of game theory, where
(separable) discrete functions of $n$ variables are referred to as (assignable)
$n$-person game forms. There is a known sufficient condition for assignability
(separability) of two-person game forms (discrete functions of two variables)
called (weak) total tightness of a game form. This property can be tested in
polynomial time, and can be easily generalized both to higher dimension and to
partially defined functions. We will prove in this paper that weak total
tightness implies separability for (partially defined) discrete functions of
$n$ variables for any $n$, thus generalizing the above result known for $n=2$.
  Keywords: separable discrete functions, totally tight and assignable game
forms
