Tag Info

Hot answers tagged

2

You've described an NP-complete problem. Indeed, this problem is exactly the subset-sum problem with the extra restriction that the desired subset has size $N$; but if this were not NP-complete then the subset-sum problem would not be either, because it would only take $|C|$ iterations of the "change-problem" algorithm to solve subset-sum (where $C$ is the ...


2

HINT: Start with an $X\in F$. Since $F\mathrel{R}G$, there is a $Y\in G$ such that $X\subseteq Y$. Then since $G\mathrel{R}F$, there is an $X'\in F$ such that $Y\subseteq X'$, and it follows that $X\subseteq X'$. But $X$ and $X'$ are both members of the partition $F$, so what does that tell you about them? What can you then infer about $X$ and $Y$?


2

For part A, for each odd integer $2k+1$ with $k$ a positive integer, consider the integers $(2k+1)2^m$ with $m$ a non-negative integer. The admissible parts in the first case include only $2k+1$ (i.e. $m=0$), whereas the admissible parts in the second case include all these integers for all $m$. In a given partition, we can group all parts with a given $k$ ...


2

By "almost equal", you mean "almost everywhere equal". Which means that the two functions agree except possibly on a set of measure zero. You can kind of visualize the measure of a subset of the real line as being its "length". And in fact, this is exactly what the measure is for intervals: that is, the measure of $(a,b)$ is $b-a.$ Now, what we call ...


1

Concerning the current edition of your question, I can say that both propositions are right, by The Sierpiński Theorem. I recall that a continuum is a compact connected Hausdorff space and remark that the unit segment $[0,1]$ can contain at most a countable family of pairwise disjoint nondegenerate closed intervals. (cited from “General Topology” by ...


1

HINT: I’ll write $F\preceq G$ instead of $F\mathrel{R}G$. You can’t assume that $H$ is the greatest lower bound, because at this point in the argument you don’t know that the set $\{F,G\}$ necessarily even has a greatest lower bound. What you need to do is show that if $H$ is any lower bound for $\{F,G\}$, then $H\preceq F\cdot G$. In order to do this, you ...


1

So you want to reduce the partition problem to the subset sum problem. Hint: Given an instance of the partition problem, sum the numbers and halve the sum to find out what each side of an equal partition must sum to. Append minus this number to the problem, and feed the resulting multiset to the hypothesized subset-sum solver.


1

I don't think there is a name for such a transform, although I could be wrong. It's pretty easy to compute using generating functions. If $a_n$ is your original sequence, let $$f(x) = \prod_{i=1}^\infty (1-x^i)^{-a_n}.$$ Then the coefficients of $f(x)$ are the transform of your sequence. In your example, we we have $a_1 = 2, a_2 = 1$, and then $$f(x) = ...



Only top voted, non community-wiki answers of a minimum length are eligible