Book chapter 182 views
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions
Eike Neumann
Lecture Notes in Computer Science, Volume: (LNCS,volume 14235), Pages: 98 - 112
Swansea University Author: Eike Neumann
Full text not available from this repository: check for access using links below.
DOI (Published version): 10.1007/978-3-031-45286-4_8
Abstract
We study the computational complexity of a robust version of the problem of testing two univariate C-finite functions for eventual inequality at large times. Specifically, working in the bit-model of real computation, we consider the eventual inequality testing problem for real functions that are sp...
| Published in: | Lecture Notes in Computer Science |
|---|---|
| ISBN: | 9783031452857 9783031452864 |
| ISSN: | 0302-9743 1611-3349 |
| Published: |
Cham
Springer Nature Switzerland
2023
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa64077 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
We study the computational complexity of a robust version of the problem of testing two univariate C-finite functions for eventual inequality at large times. Specifically, working in the bit-model of real computation, we consider the eventual inequality testing problem for real functions that are specified by homogeneous linear Cauchy problems with arbitrary real coefficients and initial values. In order to assign to this problem a well-defined computational complexity, we develop a natural notion of polynomial-time decidability of subsets of computable metric spaces which extends our recently introduced notion of maximal partial decidability. We show that eventual inequality of C-finite functions is polynomial-time decidable in this sense. |
|---|---|
| Item Description: |
Part of Book Series: Lecture Notes in Computer Science (LNCS, volume 14235) |
| College: |
Faculty of Science and Engineering |
| Start Page: |
98 |
| End Page: |
112 |