P-completeness of testing solutions of parametric interval linear systems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10419308" target="_blank" >RIV/00216208:11320/20:10419308 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-030-40814-5_14" target="_blank" >https://doi.org/10.1007/978-3-030-40814-5_14</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-40814-5_14" target="_blank" >10.1007/978-3-030-40814-5_14</a>
Alternative languages
Result language
angličtina
Original language name
P-completeness of testing solutions of parametric interval linear systems
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
50201 - Economic Theory
Result continuities
Project
<a href="/en/project/GA18-04735S" target="_blank" >GA18-04735S: Novel approaches for relaxation and approximation techniques in deterministic global optimization</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Decision Making under Constraints
ISBN
978-3-030-40813-8
ISSN
—
e-ISSN
—
Number of pages
7
Pages from-to
117-123
Publisher name
Springer
Place of publication
Cham
Event location
Tokyo, Japan
Event date
Sep 10, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—