Decomposition of arithmetical np-hard problems

Abstract

Many computational problems can be expressed as finite sums of products of simple real functions. A method is presented to computational optimization of a sum of products over finite state space. The problem is reduced to searching for the optimal decomposition of a hypergraph defined by structure of the sum. The method is compared with Lauritzen and Spiegelhalter's method used for probability calculations on causal networks which is a special case of the problem under consideration.

Keywords:

• NP-hard problem
• hypergraph
• causal network

C.R. Classification::

• G.2.1.
• G.2.2.
• G.3