Thursday, October 28, 2004

Solving an 86-Year Old Open Problem


  1. I am very sorry to disturb you but I hope you have a few seconds to answer my questions. I have read quite a lot of materials but did not find an answer. (I need it because one of my problems is reduced to IQP)
    What is a current status of NP-membership of Integer Quadratic Programming?
    Garey & Johnson mention that the problem of rational QP is in NP if all quadratic coefficients in an objective function are positive. What happens if the problem is defined as Integer QP with positive cofficients. (I have found that it is only proofed that it is in PSPACE, but without restriction on an objective function)