Ballerstein, K: Logical Interaction Networks in Biology: The

that the integer programming approach is computationally feasible. The basic SAT problem can additionally be translated into a bipartite digraph for which algorithms are adapted, and their practical use is discussed. Furthermore, for a special class of biological units a duality framework based on linear programming duality is derived, which completes the theory of such biological units.
The dynamic extension of the basic framework yields a related SAT problem that contains the original one as a special case, and is thus hard to solve as well. The focus for this extension is on the analysis of maximally feasible and minimally infeasible solutions of the extended SAT problem. Therefore, it is necessary to optimize over the set of solutions of the SAT problem which suggests to employ the equivalent integer programming approach. To enumerate all maximally feasible and minimally infeasible solutions the Joint Generation algorithm is utilized. To this end, a monotone reformulation of the extended SAT problem is derived that preserves the maximally feasible and minimally infeasible solutions, and at the same time significantly reduces the size of the description. In certain very restrictive cases the resulting integer optimization problems are even computationally tractable. Finally, the minimally infeasible solutions are completely characterized by means of graph structures in the original digraph, and an alternative method for computing all minimally infeasible solutions via polyhedral projection is obtained.
The discrete extension of the logical framework leads to a generalization of the SAT problem, the so called interval satisfiability problem. In this setting the variables are integer valued and associated intervals provide the set of values for which the expression becomes TRUE. To computationally determine feasible solutions, this problem is transformed to a system of polynomials which can be checked for feasibility by means of Hilbert's Nullstellensatz. Moreover, the general interval satisfiability problem is analyzed with respect to complexity and satisfiability. Concerning the computational complexity, it is shown to be generally hard even if assuming certain restrictions for the formulas. Concerning the satisfiability behavior the well known threshold phenomenon of classical random SAT, which has been observed for interval satisfiability, is examined and lower bounds on specific thresholds are identified.