Unconventional complexity measures for unconventional computers

Journal article

Unconventional computers—which may, for example, exploit chemical/analogue/quantum phenomena in order to compute, rather than electronically implementing discrete logic gates—are widely studied in both theoretical and practical contexts. One particular motivation behind unconventional computation is the desire efficiently to solve classically difficult problems—we recall chemical-computer attempts at solving NP-complete problems such as the Travelling Salesperson Problem—, with computational complexity theory offering the criteria for judging this efficiency. However, care must be taken here; conventional (Turing-machine-style) complexity analysis is not always appropriate for unconventional computers: new, non-standard computational resources, with correspondingly new complexity measures, are often required. Accordingly, we discuss in the present paper various resources beyond merely time and space (and, indeed, discuss various interpretations of the term ‘resource’ itself), advocating such resources’ consideration when analysing the complexity of unconventional computers. We hope that this acts as a useful starting point for practitioners of unconventional computing and computational complexity.

Authors: Blakey, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Natural Computing
• Volume: 10
• Issue: 4
• Pages: 1245-1259
• Publication date: 2011-12-01
• Edition: Author's Original
• DOI: 10.1007/s11047-010-9226-9
• EISSN: 1572-9796
• ISSN: 1567-7818
• Language: English
• Keywords: precision; computational resources; complexity; factorization; unconventional computation
• Subjects: Computer science (mathematics)