Interval-valued computation: Difference between revisions

Revision as of 13:14, 29 June 2008

Revision as of 13:15, 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]]. 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, causing that the computation power of this paradigm fits into the framework of [[Church-Turing thesis]]<ref>[[#NaVa07|Nagy & Vályi 2008]]: 14</ref> unlike [[real computation]]: interval-valued computation is not corresponding to 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>