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