A pseudo boolean function f:{0,1}^n-> R is defined as f(x)= x^tQx +cx where Q is a symmetric matrix with null elements in the diagonal. Finding the minimum of this function is solvable in polynomial time if all entries are non - positive. My question is: Remains the problem of finding the minimum polynomial, if we add linear constraints which themselves decribe a flow. More exactly: Each variable in the constraints occurs in exactly two different equalities and one time its coefficient is 1 and one time its coefficient is -1.

Many thanks for response beforehand!

  • 1
    $\begingroup$ What do you mean by "finding the minimum polynomial"? Can you specify the problem more carefully? $\endgroup$ – D.W. Jun 30 '17 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.