1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 6(55)'2006
  5. Про розпізнавальний та обчислювальний варіанти завдання "здійснимість"

Про розпізнавальний та обчислювальний варіанти завдання "здійснимість"

С.В. Лістровий, Є.С.Лістрова
Анотації на мовах:

У роботі показано, що варіант розпізнавання чи здійснима довільна булева функція чи ні, поліноміальний вирішуваний, а обчислювальний варіант завдання, коли потрібно вказати набір змінних, на якому функція приймає значення «істинно», має експоненціальну складність.