On the complexity of the satisfiability problem for a system of functional Boolean equationsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 28 мая 2015 г.
Аннотация:We consider functional Boolean equations and the satisfiability problem for them, which amounts to the following: Does there exist a Boolean function satisfying a given functional equation? We establish upper and lower bounds for the complexity of the satisfiability problem for a system of functional Boolean equations. This justifies the impossibility of its solution by any method substantially simpler than the brute-force search.