Todos os estados possíveis de um puzzle e todos os movimentos válidos entre estados constituem o espaço do problema. Trata-se da representação mental ou formal de um problema que inclui o estado inicial, o estado objetivo e os operadores que transformam um estado noutro.

Newell e Simon introduziram o conceito na sua análise da resolução de problemas humanos. A pesquisa dentro do espaço do problema pode ser exaustiva ou guiada por heurísticas que reduzem o número de caminhos considerados. O tamanho e a estrutura do espaço determinam a dificuldade. Os especialistas reduzem o espaço de forma eficaz, reconhecendo direções promissoras; os novatos exploram frequentemente de forma improdutiva.

Os problemas bem definidos possuem espaços claramente especificados; problemas mal definidos exigem que o solucionador construa o próprio espaço. A compreensão dos espaços dos problemas auxilia no desenvolvimento de instruções, ferramentas de apoio à decisão e algoritmos de pesquisa em inteligência artificial. A forma como um problema é formulado estabelece os limites dentro dos quais as soluções podem surgir.

• Representação de estados e operadores num problema
• Inclui estado inicial, objetivo e movimentos legais.
• A pesquisa pode ser sistemática ou heurística.
• A especialização reduz o espaço de pesquisa efetivo.