Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Advances in Unconventional ComputingUnconventional Computers and Unconventional Complexity Measures

Advances in Unconventional Computing: Unconventional Computers and Unconventional Complexity... [Unconventional computers—for example those exploiting chemical, analogue or quantum phenomena in order to compute, as opposed to those employing the standard, digital-computer approach of electronically implementing discrete-value logic gates—are widely studied both theoretically and experimentally. One notable motivation driving this study is the desire efficiently to solve classically difficult problems—we recall for example a chemical-computer approach to the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {{NP}}$$\end{document}-complete Travelling Salesperson Problem—, with computational complexity theory providing the criteria for judging this efficiency. However, care must be taken: conventional (Turing-machine-style) complexity analyses are in many cases inappropriate for assessing unconventional computers; new, non-standard computational resources, with correspondingly new complexity measures, may well be consumed during unconventional computation, and yet are overlooked by conventional analyses. Accordingly, we discuss in this chapter various resources beyond merely the conventional time and space, advocating such resources’ consideration during analysis of the complexity of unconventional computers (and, more fundamentally, we discuss various interpretations of the term ‘resource’ itself). We hope that this acts as a useful starting point for practitioners of unconventional computing and computational complexity.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Advances in Unconventional ComputingUnconventional Computers and Unconventional Complexity Measures

Part of the Emergence, Complexity and Computation Book Series (volume 22)
Editors: Adamatzky, Andrew
Blakey, Ed
Advances in Unconventional Computing — Jul 19, 2016
Download PDF
17 pages

Loading next page...
 
/lp/springer-journals/advances-in-unconventional-computing-unconventional-computers-and-gQvGHuOM58
Publisher
Springer International Publishing
Copyright
© Springer International Publishing Switzerland 2017
ISBN
978-3-319-33923-8
Pages
165 –182
DOI
10.1007/978-3-319-33924-5_7
Publisher site
See Chapter on Publisher Site

Abstract

[Unconventional computers—for example those exploiting chemical, analogue or quantum phenomena in order to compute, as opposed to those employing the standard, digital-computer approach of electronically implementing discrete-value logic gates—are widely studied both theoretically and experimentally. One notable motivation driving this study is the desire efficiently to solve classically difficult problems—we recall for example a chemical-computer approach to the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {{NP}}$$\end{document}-complete Travelling Salesperson Problem—, with computational complexity theory providing the criteria for judging this efficiency. However, care must be taken: conventional (Turing-machine-style) complexity analyses are in many cases inappropriate for assessing unconventional computers; new, non-standard computational resources, with correspondingly new complexity measures, may well be consumed during unconventional computation, and yet are overlooked by conventional analyses. Accordingly, we discuss in this chapter various resources beyond merely the conventional time and space, advocating such resources’ consideration during analysis of the complexity of unconventional computers (and, more fundamentally, we discuss various interpretations of the term ‘resource’ itself). We hope that this acts as a useful starting point for practitioners of unconventional computing and computational complexity.]

Published: Jul 19, 2016

Keywords: Turing Machine; Computer Computer; Time Time; Travelling Salesperson Problem; Normal Resource

There are no references for this article.