Peter Taylor
• Member for 11 years
• Last seen more than 1 year ago
• Spain

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 ...

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 ...

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'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 ...

@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 ...

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 ...

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$...

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 ...

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 ...

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 ...

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.

Sure, you can reduce it to a factor of 1, but probably at the cost of time. But to answer the question behind the question: multiplication of polynomials mod 2 is easier from a hardware point of view (...

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 ...

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 ...

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 ...

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 ...

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 ...

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+...