This section contains a proof that a specific set of macros learned by MICROHILLARY is complete with respect to the heuristic function h defined in Table 19, and that a problem solver that uses these macros can solve any solvable NxN puzzle problem in O(N^{3}) with a reasonable constant. The proof can be easily generalized to specify sufficient conditions for a set of macros to be complete.
Proof:
Let
,
and
.
The following basic operators will decrease the value of h:
(4) 

Proof:
By Lemma 1, we need to prove only for the cases where
.
There are four possible cases. Tables 20 and
21
show which operator can
be applied
in each of the cases to decrease the value of h.
To make the proof simpler, the tables assume N > 4.

Proof:
By Lemma 2, we can move from each state to a state
with a lower heuristic value. Therefore, after a finite number
of states, we will reach the state s with h(s,s_{g})=0, which is
the goal
state. N^{2} tiles are moved into their goal location.
The maximum distance of each tile from its goal location is 2(N1).
Each movement of a tile towards its goal location involves moving the blank
tile to be adjacent to the next tile, and then using either a basic
operator or a macro operator to advance the next tile.
At the beginning of this operation the blank tile can be anywhere, so
we need to advance it at most (N1)+(N2) times to bring it to
distance 1 from the
next tile. After that, for the remaining 2(N1)1 times,
a macro operator can move the blank away from the next
tile, but the distance will be at most 4 (this is a property of the
specific M), so we will need to advance it at most 3 times
to bring it next to the
next tile. By Lemma 1, the blank tile can be brought
to distance 1 using only basic operators.
After bringing the empty tile next to the next tile,
in the worst case, the algorithm may try all the 4 basic operators and
all the macros (with a total length of 124) before
finding the one that reduces the heuristic value.
All this leads to the following bound on the
total number of basic operators applied while solving a problem p
using B and M:
We can use the same lemmas to prove that MICROHILLARY can solve any solvable problem in O(N^{3}) even without learning simply by performing BFS search in each place where a macro is used in the original proof. However, instead of using 128 in the above formula, we will use 4^{18} (18, the length of the longest macro, can be used as an upper bound on the depth of the search). This gives a bound of 137,438,953,504N^{3}  137,438,953,520N^{2}, which is about 477,218,588 times larger than the constant for MICROHILLARY after learning. While in the pure sense of computational complexity both bounds belong to the same complexity class, the huge constant makes this fact meaningless for any practical purpose.