It's certainly possible to simplify the presentation: A graph $G = (V, E)$ A weight function $w_1 : V \mapsto \mathbb{N}$ A weight function $w_2 : E \mapsto (\mathbb{N} \cup \{-\infty\})$. This ...

From the set of $2^m$ possible allocations, only $m+1$ allocations can be attained by the above procedure. Why? The boundary between the two halves of the allocation is the line $w_xx = w_yy$; the ...

If the vertex pair $(u, v)$ is not in $E$ then they can't be on opposite sides of the partition, so they must be in the same half. Create a union-find data structure and merge every vertex pair which ...

As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set. No, it's just a selection problem, for which there are well-known ...

You'd have to tweak the limits (in particular max_level may be too low), but for at least some "real" problems this is within the bounds of Knuth's algorithm M. See also The documentation of ...

This has been studied in the case of the specific linear equation $$x + y = w + z$$ where (allowing trivial solutions such as $x=w, y=z$) the set $S$ is a Golomb ruler / Sidon set. In this case, the ...

This is equivalent to the property that you can construct a Hamiltonian path by greedily taking an arbitrary edge at every vertex. Searching for greedy Hamiltonian path turned up: Greedily ...

It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&2&\ldots&n\\ (k+1)\bmod n&(k+2)\bmod n&\ldots&(k+n)\bmod n\end{matrix} \right)$$ be the shift permutation. Then ...

There are $\sum_{j=1}^4 \binom{11}{j} = 561$ smaller subsets, and each $x^\phi$ contains $\sum_{j=1}^4 \binom{5}{j} = 30$ of them. If you put all $462$ $5$-element sets in a priority queue with ...

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 2500 easily ...

Your question states: However, the instruction set as devised by Babbage seems to support only going back or jumping ahead one single punched card. However, the link you supply as a reference for ...

I've rethought this and my initial bound was correct. In the worst case, $|S| = \Theta(m \; 2^\frac{m}{\lg m})$ Proof is in two parts. Firstly, $|S| = O(m \; 2^\frac{m}{\lg m})$. Consider the ...

You can avoid the multiple passes over the same elements by using a union set data-structure. One pass over each element $s$ unioning the set containing $s$ with the set containing $f(s)$. This still ...

Topological sort ($O(m+n)$) then work down it propagating a bitset of nodes from which each node can be reached ($O(m n)$). After the topological sort you can do a $O(n)$ quick-rejection (if node $n+... View answer Accepted answer 6 votes You're right to look for a reduction from the subset-sum problem. The subset problem is to find a subset$S'$of$S$such that$\Sigma_{s' \in S'} s' = t$. But this can be reduced to ... View answer 6 votes @Dave Clarke, L = a*|b* would be circular, but L* would be (a|b)*. In terms of decidability, a language$L$is circular if there is an$L'$such that$L$is the closure under + of$L'$or if ... View answer 2 votes What is$f$? I seems that you're asking for a one-to-one mapping between a power set over a power set of edges and the edges - which would surely be possible only if there's no more than one edge. View answer 5 votes Because of the crazy system on this site I can't comment directly, but I have a couple of observations on existing answers. I'm pretty sure Hsien-Chih Chang's solution needs to correct$A^2$to$AA^T\$...