Linearizability of n-linear Sirups

Abstract

Abstract A linear program is easier to evaluate than a nonlinear programo Hence, given a recursive program, it is desirable to find an equivalent linear programo However, not all nonlinear programs are linearizable. Theoretically, an m-linear program is easier to evaluate than an nlinear program when m < n, since the derivation tree 01 the lormer one is 01 smaller arity than the derivation tree 01 the latter. Thus, when an n-linear program is not linearizable, we would like to find another, equivalent m-linear program with m < n. In this paper, we consider two possibilities 01 linearizing n-linear sirups. First, we consider the equivalence between an n-linear sirup and its derivative or its general ZYT-linearization, which are linear programs. We show that the problem 01 determining whether an n-linear sirup 1.S equivalent to its derivatíve or to its general ZYT-linearization 1.S NP-hard. We then give a tighter condition which 1.S necessary and sufficient lor testing those equivalen ces. The other possibility is to consider the equivalence between an n-linear sirup and another m-linear program, m < n, called its k-ZYTlinearization, where k = n-m. We also prove that the problem 01 determining whether an n-linear sirup is equivalent to its k -ZYT -linearization is NP-hard. Then, we present a tighter, exact condition lor testing whether an n-linear sirup is equívalent to its k-ZYTlinearization. We do not know whether testing any 01 the above equivalences is decidable.