<blockquote>
  <p>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. </p>
</blockquote>

<p>The assumptions are the following: </p>

<ol>
<li><blockquote>
  <p>The simplest model studied is a state space</p>
</blockquote></li>
<li><blockquote>
  <p>that has a single goal </p>
</blockquote></li>
<li><blockquote>
  <p>and is essentially a tree with reversible actions. </p>
</blockquote></li>
</ol>

CC BY-SA 3.0
2018-04-11T15:07:02.527Z
2018-04-11T15:07:02.527Z
FreezePhoenix
<p>I am reading the cornerstone book, &quot;Artificial Intelligence, A Modern Approach&quot; by Stuart Russel, and Peter Norvig, and there is a passage in the book on page 98:</p>
<blockquote>
<p>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 8-puzzle satisfies the first and third of these
assumptions.)</p>
</blockquote>
<p>What are the &quot;assumptions&quot; in that context?</p>

<terminology><search><norvig-russell><state-spaces>
Which "assumptions" made about the state space are Russell and Norvig referring to in their book?
tahasozgen
# Which "assumptions" made about the state space are Russell and Norvig referring to in their book?

(Asked by: username_0 on 2018-04-11)

I am reading the cornerstone book, "Artificial Intelligence, A Modern Approach" by Stuart Russel, and Peter Norvig, and there is a passage in the book on page 98:

> 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 8-puzzle satisfies the first and third of these
> assumptions.)

What are the "assumptions" in that context?

**Tags:** terminology, search, norvig-russell, state-spaces


---

## 1 answers

### Answer by username_1 on 2018-04-11. Score: 0 | Accepted answer

> 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:

1. > The simplest model studied is a state space
2. > that has a single goal
3. > and is essentially a tree with reversible actions.


---

