Apples & oranges? Comparing unconventional computers

Journal article

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.

Authors: Blakey, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: North Atlantic University Union (NAUN)
• Journal: International Journal of Computers
• Volume: 4
• Issue: 4
• Pages: 185-192
• Publication date: 2010-01-01
• Edition: Publisher's version
• EISSN: 1998-4308
• Language: English
• Keywords: computational complexity; computational resource; unconventional computation; dominance; theoretical computer science
• Subjects: Computer science (mathematics)