Pseudo-boolean function

A pseudo-Boolean function is a mathematical mapping from a set of binary values to a set of real numbers. It is defined as a function f that takes a set of n-dimensional binary vertices X and maps them to a set of real numbers R. The minimization of a submodular pseudo-Boolean function can be solved in polynomial time, and the transformation to a quadratic pseudo-Boolean function requires the addition of only two binary auxiliary variables, making it computationally efficient.From: A Novel Method for Solving Simultaneous Equations in Boolean/Switching Algebra [2018], Signal Processing and Machine Learning for Biomedical Big Data [2018], Image Processing and Analysis with Graphs [2012]

Dynamic Processes on Complex Networks

View Chapter

Purchase Book

Published in Ervin Sejdić, Tiago H. Falk, Signal Processing and Machine Learning for Biomedical Big Data, 2018

June Zhang, José M.F. Moura

We showed in Ref. [21] that in regime II, solving the MPCP is equivalent to minimizing a submodular function [28]. Ref. [29] proved that the minimization of a pseudo-Boolean function that is submodular can be solved in polynomial time. Using the Max-Flow/Min-Cut algorithm proposed in Ref. [30], we can find the most-probable configuration for a network consisting of 4941 nodes, meaning that the number of configurations is 24941, in less than 0.1 sec on a desktop with 3.7 GHz Quad Core Xeon processor and 16 GB of RAM.

A Novel Method for Solving Simultaneous Equations in Boolean/Switching Algebra

View Article

Journal Information

Published in IETE Journal of Education, 2018

Pramode Ranjan Bhattacharjee

Pseudo-Boolean function: A pseudo-Boolean function (PB function) [15] is a mapping f: Bn → R, B = {0, 1} from the set of real n-dimensional vertices X = (x1x2 …xn), xj ε B, j = 1, 2, … , n into the field R of real numbers.

Pseudo-boolean function

Explore chapters and articles related to this topic

Dynamic Processes on Complex Networks

A Novel Method for Solving Simultaneous Equations in Boolean/Switching Algebra