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

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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 23

Variation on Subset Sum Problem

Hi, is the following problem NP-Complete? $L=\{<A,t>|A\subset \mathbb {Z} ,t\in \mathbb {Z} ,\ \exists \{x_{i}\}(\sum _{i}{A_{i}\cdot x_{i}}=t,\ \exists i(x_{i}\in [0,1],\forall j\neq i\ x_{j}\in \{0,1\}))\}$ עברית (talk) 05:44, 23 June 2016 (UTC)

If I understand your notation you're basically taking the subset sum problem and relaxing it a bit to allow one of the variables (which one to be decided by the algorithm, not as an input) to take on any value between 0 and 1 rather than being either 0 or 1. At first I thought that this was close enough to the subset sum problem that it would have to NP-hard as well, but now I'm pretty sure you can solve it in polynomial time. First, transform the problem into one where all the elements of A are non-negative. To do this, for each element which is negative, say a_l<0, replace a_l with -a_l, the variable x_l with 1-x_l and t with t+a_l. A bit of manipulation shows this is equivalent to the original problem except that you might have introduced some duplicate entries in the list of elements of A. Duplicates don't affect the reasoning to follow so just allow A to be a multiset. This process takes polynomial time and at the end you have an equivalent problem with all entries in A non-negative. I claim that the problem now has a solution iff 0≤t≤ΣA. In fact if a_m is the largest element of A then we can take i=m. The ⇒ direction is trivial. To see that the ⇐ direction is true, let A'=A/{a_m} and consider the set T'={ΣB:B⊆A'}. We have T' is a subset of the numbers from 0 to ΣA'. Also, the gaps between the consecutive elements of T' must all be ≤ a_m, since if u=ΣB∈T' and b∈B, then u-b=Σ(B\{b})∈T' and u-(u-b)≤b<a_m. Then T'+[0, a_m] has no gaps, and so is the interval [0, ΣA]. But [0, a_m] = {x_ma_m: x_m ∈ [0, 1] and we are done. This isn't constructive in that you just get a yes/no answer, but it's easy to use the reasoning to make it constructive and exhibit a solution if one exists. --RDBury (talk) 00:02, 24 June 2016 (UTC)

With all the elements of A positive, order them from smallest to largest. Set the x coinciding with the smallest equal to 1, then the one coinciding with the next smallest equal to 1, and so on until the element A_k runs you over the limit t. Then x_k has to be somewhere between 0 and 1 but less than 1. Set all subsequent x 's equal to 0. So the problem has a solution provided the A 's sum to at least t. Or, you could start at the largest and work down. For that matter, you could just pick them randomly until one runs you over the limit, and set that one to between 0 and 1. Loraof (talk) 02:53, 24 June 2016 (UTC)

Thank you both! I was sure it's NP-complete, and you totally convinced me that it's in P. עברית (talk) 16:12, 24 June 2016 (UTC)

Theorem on polynomial roots

Is there a theorem that goes like this?:

Let x₀ be an irrational root of a polynomial p of degree n but not of any lower-degree polynomial. Then x₀ is a root of no other, non-trivially different, polynomial of degree n.

Second question: How about if irrational in the above is replaced with non-real? Loraof (talk) 16:34, 23 June 2016 (UTC)

The polynomial is assumed to have integer coefficients as any number x₀ is root in x−x₀.

If n=1 then the roots are rational.

If n>1 then the roots are irrational, unless they are also roots in a polynomial of degree 1.

Bo Jacoby (talk) 17:01, 23 June 2016 (UTC).

Right, the word irrational was not needed in the potential theorem statement. The question remains as to whether such a theorem exists. Loraof (talk) 17:17, 23 June 2016 (UTC)

The polynomials f in Q[x] for which f(x₀)=0 form an ideal. Since Q[x] is a P.I.D. the ideal is generated by a single polynomial f₀. This f₀ is called the minimum polynomial and would have to be of degree n. If g is a polynomial of degree n so that g(x₀)=0 then g would have to be a constant multiple of f₀, in other words not trivially different. --RDBury (talk) 18:37, 23 June 2016 (UTC)

See Minimal polynomial (field theory) §Alternative proof of uniqueness (can't seem to get a working link to that sub-section). Essentially, it says that if you have two polynomials of degree n and they share a common root x₀, then any linear combination of the two also has a root x₀. If your two polynomials are not simply constant multiples of the same thing, then you can choose a linear combination which eliminates the leading term to leave a polynomial of lower degree with a root x₀. --catslash (talk) 18:53, 23 June 2016 (UTC)

I get it—thanks! Loraof (talk) 19:57, 23 June 2016 (UTC)