On the Hardness of Problems Involving Negator Relationships in an Artificial Hormone System
The Artificial Hormone System (AHS) is a self-organizing middleware to allocate tasks in a distributed system. We extended it by so-called negator hormones to enable conditional task structures. However, this extension increases the computational complexity of seemingly simple decision problems in the system: In [1] and [2], we defined the problems Negator-Path and Negator-Sat and proved their NP-completeness. In this supplementary report to these papers, we show examples of Negator-Path and Negator-Sat, introduce the novel problem Negator-Stability and explain why all of these problems involving negators are hard to solve algorithmically.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Contracting and Involutive Negations of Probability Distributions
A dozen papers have considered the concept of negation of probability distributions (pd) introduced by Yager. Usually, such negations are generated point-by-point by functions defined on a set of probability values and c…
NegationGenerating Negations of Probability Distributions
Recently it was introduced a negation of a probability distribution. The need for such negation arises when a knowledge-based system can use the terms like NOT HIGH, where HIGH is represented by a probability distributio…
NegationThe Effect of Negators, Modals, and Degree Adverbs on Sentiment Composition
Negators, modals, and degree adverbs can significantly affect the sentiment of the words they modify. Often, their impact is modeled with simple heuristics; although, recent work has shown that such heuristics do not cap…
A review of sentiment computation methods with R packages
Four packages in R are analyzed to carry out sentiment analysis. All packages allow to define custom dictionaries. Just one - Sentiment R - properly accounts for the presence of negators.
Sentiment AnalysisFrom Local Pseudorandom Generators to Hardness of Learning
We prove hardness-of-learning results under a well-studied assumption on the existence of local pseudorandom generators. As we show, this assumption allows us to surpass the current state of the art, and prove hardness o…
PAC learning