# Tag Info

3

Given a graph, does it have a cycle of length $3$ ($4$)? Four-cycles there is an easy algorithm that requires $O(n^2)$ time. The best known algorithm for triangle detection is related to matrix multiplication and has complexity $O(n^\omega)$ where $\omega$ is the matrix multiplication exponent. It is an open problem to determine whether $\omega=2$. Given a ...

2

This is essentially the same problem as partition. Let $M$ be a large enough integer, and replace each tuple $(a_{i1},\ldots,a_{ik})$ with the single integer $\sum_j a_{ij} M^j$. You now have an equivalent instance of PARTITION. Your problem appears in the literature, under the name multidimensional two-way number partitioning, in Jelena Kojić, Integer ...

2

In 1966, I was taught by Professor Tom Kilburn at Manchester University. He said the half adder was sometimes called the Kilburn adder because he invented it!

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