Wikipedia:Reference desk/Archives/Mathematics/2016 June 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 25

Variation on Qudratic Programming

Is the following problem NP-complete? $L=\{<Q,\lambda >|Q\ is\ n\times n\ matrix,\ ,\lambda \in \mathbb {R} ,\ \exists x(x^{T}Qx<\lambda ,\ \exists i(x_{i}\in [0,1],\forall j\neq i\ x_{j}\in \{0,1\}))\}$ עברית (talk) 07:53, 25 June 2016 (UTC)

There is always a solution: set all x's equal to 0. Loraof (talk) 15:02, 25 June 2016 (UTC) That's assuming lambda is positive. Loraof (talk) 15:04, 25 June 2016 (UTC)

After thinking about it for a while, it seems NP-hard to me, but I can't find a proof of that. Loraof (talk) 19:49, 25 June 2016 (UTC)

I don't assume that $\lambda$ is positive. (nor I assume Q's entries to be positive) 132.67.104.216 (talk) 15:24, 26 June 2016 (UTC)

I'm not an expert but AFAIK questions of computability and complexity are usually asked about countable sets. The inputs and witnesses are based on integers. I think you have wholly different questions when you put real numbers in the mix. A classical Turing machine can't operate on real numbers.

That said, I think the problem will not materially change if you replace all occurrences of real numbers with rational numbers, and then I think they can be handled safely. -- Meni Rosenfeld (talk) 10:49, 27 June 2016 (UTC)