Interval computers are a special kind of theoretical models for computation that are capable of working on “interval-valued bytes”: special subsets of the (0, 1) real interval. Thus, they can be regarded as kind of ideal analog computers. If they 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.[1] “The validity problem of quantified propositional formulae is decidable by a linear interval-valued computation. As a consequence, all polynomial space problems 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).[2]
See also
Notes
References
- Tajti, Ákos (June 20, 2008). Solving Tripartite Matching by Interval-valued Computation in Polynomial Time. Computability in Europe 2008. Logic and Theory of Algorithms. pp. 208–222.
{{cite conference}}: External link in|conferenceurl=|coauthors=ignored (|author=suggested) (help); Unknown parameter|conferenceurl=ignored (|conference-url=suggested) (help) See short abstract. - Nagy, Benedek (April 8, 2008). "Interval-valued computations and their connection with PSPACE". Theoretical Computer Science (Preface: From Gödel to Einstein: Computability between Logic and Physics). 394 (3): 208–222.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help)
 | This computer science article is a stub. You can help Wikipedia by expanding it. |