Which "assumptions" made about the state space are Russell and Norvig referring to in their book?
The complexity results depend very strongly on the assumptions made about the state space. The simplest model studied is a state space that has a single goal and is essentially a tree with reversible actions. 


The assumptions are the following: 



  The simplest model studied is a state space


  that has a single goal 


  and is essentially a tree with reversible actions.