%0 Journal Article 
%A Mulero Martínez, Juan Ignacio
%T A polynomial-time algorithm for optimization of quadratic pseudo-boolean functions
%D 2020
%U http://hdl.handle.net/10317/10351
%X We develop a polynomial-time algorithm to minimize pseudo-Boolean functions. The computational complexity is O(n □(15/2)), although very conservative, it is su_cient to prove that this minimization problem is in the class P. A direct application of the algorithm is the 3-SAT problem, which is also guaranteed to be in the class P with a computational complexity of order O(n □(45/2)). The algorithm was implemented in MATLAB and checked by generating one million matrices of arbitrary dimension up to 24 with random entries in the range [-50; 50]. All the experiments were successful.
%K Computer science
%K Optimization
%K Computer software
%K MATLAB
%K Mathematical software
%K Matemática Aplicada
%K 1102.02 Álgebra de Boole
%~ GOEDOC, SUB GOETTINGEN