We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Unconventional complexity measures for unconventional computers.
- Authors
Blakey, Ed
- Abstract
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 -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.
- Subjects
COMPUTER research; TURING machines; COMPUTATIONAL complexity; FACTORIZATION; COMPUTERS; QUANTUM theory
- Publication
Natural Computing, 2011, Vol 10, Issue 4, p1245
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-010-9226-9