The equivalence of connectionist energy minimization and propositional calculus satisfiability
Technical Report Number
Quadratic energy minimization is the essence of certain connectionist models. We define high order connectionist models to support the minimization of high order energy functions and we prove that high order energy functions are equivalent to quadratic ones. We show that the standard quadratic models can minimize high order functions using additional hidden units and we demonstrate trade-offs of size (number of hidden units), order of the model, and fan-out. We prove an equivalence between the problem of satisfiability in propositional calculus and the problem of minimization of energy functions. An energy function describes a Well Formed Formula (WFF) if the set of solutions to the minimization of the function is equal to the set of models (truth assignments) that satisfy the WFF. We show that every satisfiable WFF is described by some energy function and that every energy function describes some WFF. Algorithms are given to transform any propositional WFF into an energy function that describes it and vice versa. A connectionist propositional inference engine that features incremental updating of the knowledge can be implemented using these algorithms. The results have applications in reasoning and AI, and also give a better understanding of the limitations and the capabilities of connectionist energy minimization models.
Pinkas, Gadi, "The equivalence of connectionist energy minimization and propositional calculus satisfiability" Report Number: WUCS-90-03 (1990). All Computer Science and Engineering Research.
Permanent URL: http://dx.doi.org/10.7936/K7XS5SQC