Apples & oranges? Comparing unconventional computers
Complexity theorists routinely compare—via the pre-ordering induced by asymptotic notation—the efficiency of computers so as to ascertain which offers the most efficient solution to a given problem. Tacit in this statement, however, is that the computers conform to a standard computational model: th...
| Hovedforfatter: | |
|---|---|
| Format: | Journal article |
| Sprog: | English |
| Udgivet: |
North Atlantic University Union (NAUN)
2010
|
| Fag: |
| _version_ | 1826269687790436352 |
|---|---|
| author | Blakey, E |
| author_facet | Blakey, E |
| author_sort | Blakey, E |
| collection | OXFORD |
| description | Complexity theorists routinely compare—via the pre-ordering induced by asymptotic notation—the efficiency of computers so as to ascertain which offers the most efficient solution to a given problem. Tacit in this statement, however, is that the computers conform to a standard computational model: that is, they are Turing machines, random-access machines or similar. However, whereas meaningful comparison between these conventional computers is well understood and correctly practised, that of non-standard machines (such as quantum, chemical and optical computers) is rarely even attempted and, where it is, is often attempted under the typically false assumption that the conventional-computing approach to comparison is adequate in the unconventional-computing case. We discuss in the present paper a computational-model-independent approach to the comparison of computers' complexity (and define the corresponding complexity classes). Notably, the approach allows meaningful comparison between an unconventional computer and an existing, digital-computer benchmark that solves the same problem. |
| first_indexed | 2024-03-06T21:29:00Z |
| format | Journal article |
| id | oxford-uuid:440697b7-5b35-4504-b76a-092a729cd572 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:29:00Z |
| publishDate | 2010 |
| publisher | North Atlantic University Union (NAUN) |
| record_format | dspace |
| spelling | oxford-uuid:440697b7-5b35-4504-b76a-092a729cd5722022-03-26T14:59:10ZApples & oranges? Comparing unconventional computersJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:440697b7-5b35-4504-b76a-092a729cd572Computer science (mathematics)EnglishOxford University Research Archive - ValetNorth Atlantic University Union (NAUN)2010Blakey, EComplexity theorists routinely compare—via the pre-ordering induced by asymptotic notation—the efficiency of computers so as to ascertain which offers the most efficient solution to a given problem. Tacit in this statement, however, is that the computers conform to a standard computational model: that is, they are Turing machines, random-access machines or similar. However, whereas meaningful comparison between these conventional computers is well understood and correctly practised, that of non-standard machines (such as quantum, chemical and optical computers) is rarely even attempted and, where it is, is often attempted under the typically false assumption that the conventional-computing approach to comparison is adequate in the unconventional-computing case. We discuss in the present paper a computational-model-independent approach to the comparison of computers' complexity (and define the corresponding complexity classes). Notably, the approach allows meaningful comparison between an unconventional computer and an existing, digital-computer benchmark that solves the same problem. |
| spellingShingle | Computer science (mathematics) Blakey, E Apples & oranges? Comparing unconventional computers |
| title | Apples & oranges? Comparing unconventional computers |
| title_full | Apples & oranges? Comparing unconventional computers |
| title_fullStr | Apples & oranges? Comparing unconventional computers |
| title_full_unstemmed | Apples & oranges? Comparing unconventional computers |
| title_short | Apples & oranges? Comparing unconventional computers |
| title_sort | apples amp oranges comparing unconventional computers |
| topic | Computer science (mathematics) |
| work_keys_str_mv | AT blakeye applesamporangescomparingunconventionalcomputers |