Representation operators and computation

Kitts, B. (1998) Representation operators and computation. [Preprint] (Unpublished)

Full text available as:

[img] Postscript


This paper derives results about the impact of representation and search operators on the Computational Complexity of a problem. A model of computation is introduced based on a directed graph structure, and representation and search are defined to be the vertices and edges of the graph respectively. Changing either the representation or the search algorithm leads to different possible graphs, and hence different complexity classes. The final section explores the role of representation in reducing time complexity in Artificial Intelligence.

Item Type:Preprint
Keywords:representation recoding redescription
Subjects:Computer Science > Artificial Intelligence
Computer Science > Complexity Theory
Computer Science > Machine Learning
ID Code:457
Deposited By: Kitts, Brendan
Deposited On:14 Jun 1998
Last Modified:11 Mar 2011 08:53


Repository Staff Only: item control page