Interval-valued computation: Difference between revisions

Revision as of 12:12, 29 June 2008

Revision as of 12:14, 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 (0, 1) [[Intervalunit (mathematics)|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.

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>