P-completeness of testing solutions of parametric interval linear systems

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

P-completeness of testing solutions of parametric interval linear systems

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

P-completeness of testing solutions of parametric interval linear systems

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

50201 - Economic Theory

Projekt

<a href="/cs/project/GA18-04735S" target="_blank" >GA18-04735S: Nové přístupy pro relaxační a aproximační techniky v deterministické globální optimalizaci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Decision Making under Constraints

ISBN

978-3-030-40813-8

ISSN

—

e-ISSN

—

Počet stran výsledku

7

Strana od-do

117-123

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Tokyo, Japan

Datum konání akce

10. 9. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—