Milan Hladík, Michal Černý, and Vladik Kreinovich. When is data processing under interval and fuzzy uncertainty feasible: What if few inputs interact? Does feasibility depend on how we describe interaction?. In S. N. Shahbazova and others, editors, Recent Developments and the New Direction in Soft-Computing Foundations and Applications, STUDFUZZ, pp. 91–100, Springer, Cham, 2021.
[PDF] [gzipped postscript] [postscript] [HTML]
It is known that, in general, data processing under interval and fuzzy uncertainty is NP-hard - which means that, unless P = NP, no feasible algorithm is possible for computing the accuracy of the result of data processing. It is also known that the corresponding problem becomes feasible if the inputs do not interact with each other, i.e., if the data processing algorithm computes the sum of n functions, each depending on only one of the n inputs. In general, inputs $x_i$ and $x_j$ interact. If we take into account all possible interactions, and we use bilinear functions $x_i\cdot x_j$ to describe this interaction, we get an NP-hard problem. This raises two natural questions: what if only a few inputs interact? What if the interaction is described by some other functions? In this paper, we show that the problem remains NP-hard if we use different formulas to describe the inputs' interaction, and it becomes feasible if we only have $O(łog(n))$ interacting inputs - but remains NP-hard if the number of inputs is $O(n^\varepsilon)$ for any $\varepsilon>0$.
@inCollection{HlaCer2021a,
author = "Milan Hlad\'{\i}k and Michal {\v{C}}ern\'{y} and Vladik Kreinovich",
title = "When is data processing under interval and fuzzy uncertainty feasible: {What} if few inputs interact? {Does} feasibility depend on how we describe interaction?",
editor = "S. N. Shahbazova and others",
feditor = "Shahbazova, Shahnaz N. and Kacprzyk, Janusz and Balas, Valentina Emilia and Kreinovich, Vladik",
booktitle = "Recent Developments and the New Direction in Soft-Computing Foundations and Applications",
fbooktitle = "Recent Developments and the New Direction in Soft-Computing Foundations and Applications: Selected Papers from the 7th World Conference on Soft Computing, May 29--31, 2018, Baku, Azerbaijan",
publisher = "Springer",
address = "Cham",
series = "STUDFUZZ",
fseries = "Studies in Fuzziness and Soft Computing",
volume = "393",
pages = "91-100",
year = "2021",
doi = "10.1007/978-3-030-47124-8_8",
isbn = "978-3-030-47124-8",
url = "https://doi.org/10.1007/978-3-030-47124-8_8",
bib2html_dl_html = "https://link.springer.com/chapter/10.1007/978-3-030-47124-8_8",
abstract = "It is known that, in general, data processing under interval and fuzzy uncertainty is NP-hard - which means that, unless P = NP, no feasible algorithm is possible for computing the accuracy of the result of data processing. It is also known that the corresponding problem becomes feasible if the inputs do not interact with each other, i.e., if the data processing algorithm computes the sum of n functions, each depending on only one of the n inputs. In general, inputs $x_i$ and $x_j$ interact. If we take into account all possible interactions, and we use bilinear functions $x_i\cdot x_j$ to describe this interaction, we get an NP-hard problem. This raises two natural questions: what if only a few inputs interact? What if the interaction is described by some other functions? In this paper, we show that the problem remains NP-hard if we use different formulas to describe the inputs' interaction, and it becomes feasible if we only have $O(\log(n))$ interacting inputs - but remains NP-hard if the number of inputs is $O(n^{\varepsilon})$ for any $\varepsilon>0$.",
keywords = "Interval computation; NP-hardness; Quadratic form; t-form",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44