The purpose of this paper is to explore the possibility that purely graph-theoretic reasons may account for the superlinear complexity of wide classes of computational problems. The results are therefore of two kinds: reductions to graph theoretic conjectures on the one hand, and graph theoretic results on the other.
No takes yet. Share an insight, caveat, or question.
Leslie G. Valiant (1975) studied this question.