Interval computers are a special kind of theoretical models for hypercomputation, 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)