Hardness of Solving Relational Equations
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F15%3A33155572" target="_blank" >RIV/61989592:15310/15:33155572 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1109/TFUZZ.2015.2394396" target="_blank" >http://dx.doi.org/10.1109/TFUZZ.2015.2394396</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/TFUZZ.2015.2394396" target="_blank" >10.1109/TFUZZ.2015.2394396</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Hardness of Solving Relational Equations
Popis výsledku v původním jazyce
Minimal solutions play a crucial role in describing all solutions of relational equations. For this reason, the problem of computing minimal solutions has for long been examined. The literature contains several algorithms for computing minimal solutions.Recently, contributions regarding computational complexity of the problem itself appeared. The complexity aspect is clearly of fundamental importance. However, the existing results contain serious flaws. In this paper, we inspect the existing contributions, clarify the flaws, examine the problem of complexity of computing minimal solutions, prove that there is no efficient algorithm computing all minimal solutions, and discuss further ramifications of our observations.
Název v anglickém jazyce
Hardness of Solving Relational Equations
Popis výsledku anglicky
Minimal solutions play a crucial role in describing all solutions of relational equations. For this reason, the problem of computing minimal solutions has for long been examined. The literature contains several algorithms for computing minimal solutions.Recently, contributions regarding computational complexity of the problem itself appeared. The complexity aspect is clearly of fundamental importance. However, the existing results contain serious flaws. In this paper, we inspect the existing contributions, clarify the flaws, examine the problem of complexity of computing minimal solutions, prove that there is no efficient algorithm computing all minimal solutions, and discuss further ramifications of our observations.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2015
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ů
Údaje specifické pro druh výsledku
Název periodika
IEEE Transactions on Fuzzy Systems
ISSN
1063-6706
e-ISSN
—
Svazek periodika
23
Číslo periodika v rámci svazku
6
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
4
Strana od-do
2435-2438
Kód UT WoS článku
000365989300041
EID výsledku v databázi Scopus
—