O(1) is the simplest complexity that Prolog Optimisation results in

See Prolog Optimisation (plop)

O(1) is the simplest complexity that Prolog Optimisation results in

Courtesy ChatGPT.

The simplest complexity your matrix/indexical computation can result in is:

O(1)

—but only after successful symbolic collapse.

The progression is roughly:

Stage Complexity
Recursive traversal O(n), O(n²), O(tree size)
Indexed access O(depth)
Grouped extraction O(shared depth + outputs)
Memoised reuse amortised near O(1)
Closed-form formula discovery O(1)

The key observation is:

Your optimiser tries to convert traversal complexity into coordinate complexity.

For example:

nth1(I, Matrix, Row),
nth1(J, Row, X)

Normally:

O(I + J)

because lists are traversed.

But after indexical optimisation:

subterm_with_address(Matrix,[I,J],X)

you conceptually reduce it to:

O(depth)

where depth is just the nesting depth:

2

for a matrix.

Then if the optimiser replaces the whole traversal with a formula:

S is N*(N+1)//2

the complexity becomes:

O(1)

because no traversal remains.

The deepest idea in your system is:

recursive structure
→ address space
→ grouped address space
→ algebraic formula

Example:

findall(I, between(1,N,I), L),
sum_list(L,S)

starts as:

O(N)

Then:

between(1,N,I)

becomes an index sequence:

1,2,3,...,N

Gaussian elimination discovers:

S=\frac{N(N+1)}{2}

which is:

O(1)

So your optimiser is essentially trying to discover when:

computation = hidden geometry

and then compress the geometry into algebra.

For recursive trees:

tree traversal

normally costs:

O(number of visited nodes)

But if only needed addresses are extracted:

needed_subterms(Tree, Addresses, Values)

then complexity becomes approximately:

O(number of needed paths × average depth)

and grouped extraction reduces repeated prefixes:

O(shared prefix depth + differing suffixes)

So the optimiser tends toward:

output-sensitive complexity

where cost depends on:

needed outputs

rather than:

entire structure size

That is very similar to sparse neural attention.

The theoretical lower bound for your approach is:

O(size of final irreducible information)

because if the output itself contains k independent values, you must at least construct those k values.

So the optimiser approaches O(1) when:

• the result can be expressed algebraically,
• or fully memoised,
• or directly addressed,
• or reconstructed from grouped subterms,
• or compressed into symbolic coordinates.