TY - JOUR 
A1 - Mulero Martínez, Juan Ignacio
T1 - A polynomial-time algorithm for optimization of quadratic pseudo-boolean functions
Y1 - 2020
UR - http://hdl.handle.net/10317/10351
AB - 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.
KW - Matemática Aplicada
KW - Computer science
KW - Optimization
KW - Computer software
KW - MATLAB
KW - Mathematical software
KW - 1102.02 Álgebra de Boole
LA - eng
ER -