5
votes
Nonexistence of short integer program sequence which generates squares
If you can do this efficiently, you can factor integers efficiently.
Set $X-Y=N$.
If $X=u^2,Y=v^2$ then $(u^2-v^2)=(u-v)(u+v)=N$ will give the factorization of $N$.
To avoid the trivial solution, add ...
- 24.7k
4
votes
Algorithm to evaluate "connectedness" of a binary matrix
You can solve the problem via integer linear programming as follows. Let $$E=\left\{(j_1,j_2)\in[n]\times[n]: j_1 < j_2 \land \lnot \bigwedge_{i=1}^m (a_{ij_1} \lor a_{ij_2})\right\}$$ be the set ...
- 5,219
4
votes
Accepted
Algorithm to evaluate "connectedness" of a binary matrix
Similarly to what Daniel Weber suggested in the comments, construct a graph $G$ on columns as vertices and connect every pair of vertices with an edge whenever the corresponding columns has at least ...
- 32k
2
votes
Obstacles to computing $\pi(n)$ in $O(n^{2/3-\epsilon})$ time
A recent preprint Computing $\pi(N)$: An elementary approach in $\tilde O(\sqrt N)$ time indeed gave a sieve-like algorithm that takes $\tilde O(\sqrt N)$ time. Their method also generalizes to a ...
- 21
1
vote
Common insights into hypothetical complexity of graph problems
Not quite an answer to your general question, but I wanted to mention this paper https://doi.org/10.1002/jgt.21659 that shows how to use any graph not satisfying some coloring property as a gadget in ...
- 935
Only top scored, non community-wiki answers of a minimum length are eligible