Hardness of Solving Relational Equations

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Hardness of Solving Relational Equations
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)