Interval-valued computation: Difference between revisions

Revision as of 05:15, 19 March 2013

Revision as of 14:21, 29 March 2014

Line 4:

Only special subsets of the unit interval are considered; the restrictions are of finite nature, so that the computation power of this paradigm fits into the framework of [[Church-Turing thesis]]:<ref>[[#NaVa07|Nagy & Vályi 2007]]: 14</ref> unlike [[real computation]], interval-valued computation is not capable of [[hypercomputation]].

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

== Notes ==

Line 20:

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

[[Category:Computational complexity theory]]

{{comp-sci-stub}}

{{comp-sci-stub}}

[[Category:Computational complexity theory]]