Interval-valued computation: Difference between revisions

Revision as of 12:58, 29 June 2008

Revision as of 12:59, 29 June 2008

Line 1:

'''''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]]. Thus, this model can be regarded as kind of ideal [[analog computer]]. 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 concerned, the restrictiosrestrictions are of finite nature, thusthethus the paradigm fits into the framework of [[Church-Turing thesis]],<ref>[[#NaVa07|Nagy & Vályi 2008]]: 14</ref> unlike [[real computation]]

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>