Isn’t that just a SLD with a depth limit somehow. You still in the
domain of Datalog for definite clauses? Some people do
count the variables in the rules, and then get combined complexity:
|P| * |D| ^ |V|
This is not a depth limit, but a time limit. Problem is the depth limit
shows PSPACE, this then often translates exponential into some,
time limit, i.e. hence EXPTIME.
But I am a little bit rusty. LLMs probably don’t try that, don’t know
what heuristic they have in stock, they won’t do it, because of
more tight time limits and since the requirement is an interactive
session, and not some offline batch learning. If you fix the Datalog
program P , paradoxically complexity looks different. But an ILP
tries to deal with different hypothesis, so I guess
the Datalog program P also changes, right?
See also:
Complexity and Expressive Power of Datalog
https://www.cs.ox.ac.uk/files/1018/gglecture7.pdf