Interval-valued computation: Difference between revisions

Revision as of 10:30, 29 June 2008

Revision as of 10:33, 29 June 2008

Line 1:

'''''Interval computer'''''s are a special kind of theoretical models for [[hypercomputation]], as such, there are no architectures for their physical implementations. 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>[[#NaVá08NaVa08|Nagy & Vályi 2008]]</ref>

== See also ==

Line 12:

* <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>

* <cite id=NaVá08NaVa08>{{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>