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
