Comparing asymptotic sizes of state-based & causal encodings
State-based encoding with Explanatory-frame axioms is the smallest (known) state-based encoding
- O(k* (|O|+|U|)) variables
- O(k*(|O|+|U|) )clauses
Causal encoding with contiguous ordering and white-knight-based establishment is the smallest (known) causal encoding
- O(k*(|O|+|U|))variables
- O(k2*|U|) clauses
Same number of variables, but more clauses
White-knight based establishment can be seen as
a form of explanatory frame axioms
--Deals with each condition separately,
rather than by clustering them into states
--Flexibile but inefficient for our purposes
Theorem: Causal encodings are strictly
larger than best state-based encodings.