Milan Hladík. P-completeness of testing solutions of parametric interval linear systems. In Martine Ceberio and Vladik Kreinovich, editors, Decision Making under Constraints, Studies in Systems, Decision and Control, pp. 117–123, Springer, Cham, 2020.
[PDF] [gzipped postscript] [postscript] [HTML]
We deal with a system of parametric interval linear equations and also with its particular sub-classes defined by symmetry of the constraint matrix. We show that the problem of checking whether a given vector is a solution is a P-complete problem, meaning that there unlikely exists a polynomial closed form arithmetic formula describing the solution set. This is true not only for the general parametric system, but also for the symmetric case with general linear dependencies in the right-hand side. However, we leave as an open problem whether P-completeness concerns also the simplest version of the symmetric solution set with no dependencies in the right-hand side interval vector.
@inCollection{Hla2020b,
author = "Milan Hlad\'{\i}k",
title = "P-completeness of testing solutions of parametric interval linear systems",
editor = "Ceberio, Martine and Kreinovich, Vladik",
booktitle = "Decision Making under Constraints",
publisher = "Springer",
address = "Cham",
series = "Studies in Systems, Decision and Control",
volume = "276",
pages = "117-123",
year = "2020",
doi = "10.1007/978-3-030-40814-5_14",
isbn = "978-3-030-40813-8",
url = "https://doi.org/10.1007/978-3-030-40814-5_14",
bib2html_dl_html = "https://link.springer.com/chapter/10.1007/978-3-030-40814-5_14",
abstract = "We deal with a system of parametric interval linear equations and also with its particular sub-classes defined by symmetry of the constraint matrix. We show that the problem of checking whether a given vector is a solution is a P-complete problem, meaning that there unlikely exists a polynomial closed form arithmetic formula describing the solution set. This is true not only for the general parametric system, but also for the symmetric case with general linear dependencies in the right-hand side. However, we leave as an open problem whether P-completeness concerns also the simplest version of the symmetric solution set with no dependencies in the right-hand side interval vector.",
keywords = "Interval computation; Parametric system; Linear system; P-complete problem",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44