When Is Data Processing Under Interval and Fuzzy Uncertainty Feasible: What if Few Inputs Interact? Does Feasibility Depend on How We Describe Interaction?
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 and interact. If we take into account all possible interactions, and we use bilinear functions 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 interacting inputs-but remains NP-hard if the number of inputs is for any. (C) 2021, Springer Nature Switzerland AG.