Hacker News Reader

The number of edges in a complete graph is n*(n - 1)/2, so by that metric it would be quadratic.

Yes but the number of nodes is n, and an "interaction" among m nodes might not be decomposable to a chain of pairwise interactions, which raises the ceiling back to exponetial (actually factorial, which is worse).

What corresponds to interactions that aren't decomposable as pairwise interactions? Race conditions? Resource utilization? Real bugs (and the nastier ones), but probably a minority. So factorial with a relatively small constant in front of it.

But obviously the real answer is to write a program that will correctly verify all other programs.

It can be quadratic. Think about drawing all possible lines between points (possible components in software):

Make a table with columns being # points and the # lines you can draw between them.

1 0 2 1 3 3 (triangle) 4 6 (box with a criss cross) 5 10 (5 point star, with everything connected) ...

This relation is n * (n - 1) / 2

Yes, combination, which is factorial, which is yet larger than exponential.

Not sure what you mean by "geometric" in this context.