---
abstract: '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.'
altloc:
- http://www.cs.brandeis.edu/~brendy
chapter: ~
commentary: ~
commref: ~
confdates: ~
conference: ~
confloc: ~
contact_email: ~
creators_id: []
creators_name:
- family: Kitts
given: B.
honourific: ''
lineage: ''
date: 1998
date_type: published
datestamp: 1998-06-14
department: ~
dir: disk0/00/00/04/57
edit_lock_since: ~
edit_lock_until: ~
edit_lock_user: ~
editors_id: []
editors_name: []
eprint_status: archive
eprintid: 457
fileinfo: /style/images/fileicons/application_postscript.png;/457/2/duality2.ps
full_text_status: public
importid: ~
institution: ~
isbn: ~
ispublished: unpub
issn: ~
item_issues_comment: []
item_issues_count: 0
item_issues_description: []
item_issues_id: []
item_issues_reported_by: []
item_issues_resolved_by: []
item_issues_status: []
item_issues_timestamp: []
item_issues_type: []
keywords: representation recoding redescription
lastmod: 2011-03-11 08:53:58
latitude: ~
longitude: ~
metadata_visibility: show
note: ~
number: ~
pagerange: ~
pubdom: FALSE
publication: ~
publisher: ~
refereed: FALSE
referencetext: ~
relation_type: []
relation_uri: []
reportno: ~
rev_number: 10
series: ~
source: ~
status_changed: 2007-09-12 16:28:15
subjects:
- comp-sci-art-intel
- comp-sci-complex-theory
- comp-sci-mach-learn
succeeds: ~
suggestions: ~
sword_depositor: ~
sword_slug: ~
thesistype: ~
title: Representation operators and computation
type: preprint
userid: 203
volume: ~