|
#REDIRECT [[Interval arithmetic]]
'''''Interval-valued computation''''' is a special kind of theoretical models for computation. It is capable of working on “interval-valued bytes”: special subsets of the [[unit interval]]. If such computers were realized, their computation power would be much greater than that of functioning, "implementable" computers. As such, there are no architectures for their physical implementations. Only special subsets of the unit interval are considered, the restrictions are of finite nature, thus the paradigm fits into the framework of [[Church-Turing thesis]],<ref>[[#NaVa07|Nagy & Vályi 2008]]: 14</ref> unlike [[real computation]], it is not an unrestricted ideal [[analog computer]].
Such a model of computation is capable of solving [[NP-complete]] problems like [[tripartite matching]].<ref>[[#TaNa08|Tajti & Nagy 2008]]</ref> “The [[Boolean satisfiability problem#Extensions_of_SAT|validity problem of quantified propositional formulae]] is decidable by a linear interval-valued computation. As a consequence, all [[PSPACE|polynomial space problem]]s are decidable by a polynomial interval-valued computation. Furthermore, it is proven that PSPACE coincides with the class of languages which are decidable by a restricted polynomial interval-valued computation” (links added).<ref>[[#NaVa08|Nagy & Vályi 2008]]</ref>
== See also ==
* [[Real computation]]
== Notes ==
<references/>
== References ==
* <cite id=NaVa07>{{cite conference |last=Nagy |first=Benedek |coauthors=Vályi, Sándor |title=Visual reasoning by generalized interval-values and interval temporal logic |pages=13–26 |booktitle=VLL |conference=Proceedings of the VLL 2007 workshop on Visual Languages and Logic |editor=Philip T. Cox & Andrew Fish & John Howse |publisher=CEUR Workshop Proceedings |___location=Coeur d'Aléne, Idaho, USA |date=23 September 2007 |format=PDF |url=http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-274/paper2.pdf}}</cite>
* <cite id=NaVa08>{{cite journal |last=Nagy |first=Benedek |coauthors=Vályi, Sándor |title=Interval-valued computations and their connection with PSPACE |journal=Theoretical Computer Science (Preface: From Gödel to Einstein: Computability between Logic and Physics) |volume=394 |issue=3 |pages=208–222 |date=April 8, 2008 |url=http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4RDS46X-2&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=88688a8f0efc70b7e0f2e882a29ec29c}}</cite>
* <cite id=TaNa08>{{cite conference |last=Tajti |first=Ákos |coauthors=Nagy, Benedek |title=Solving Tripartite Matching by Interval-valued Computation in Polynomial Time |conference=Computability in Europe 2008. Logic and Theory of Algorithms |conferenceurl=http://www.cs.swan.ac.uk/cie08/ |date=June 20, 2008 |pages=208–222}} See short [http://www.cs.swan.ac.uk/cie08/giveabs.php?54 abstract].</cite>
== External links ==
* <cite id=NaVa07>{{cite conference |last=Nagy |first=Benedek |coauthors=Vályi, Sándor |title=Visual reasoning by generalized interval-values and interval temporal logic |pages=13–26 |booktitle=VLL |conference=Proceedings of the VLL 2007 workshop on Visual Languages and Logic |editor=Philip T. Cox & Andrew Fish & John Howse |publisher=CEUR Workshop Proceedings |___location=Coeur d'Aléne, Idaho, USA |date=23 September 2007 |format=PDF |url=http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-274/paper2.pdf}}</cite>
{{comp-sci-stub}}
[[Category:Computational complexity theory]]
[[hu:Intervallum-számítógép]]
| 