Про генеричну NP-повноту проблеми здійсненностібулевих формул

З усіх питань, пов'язаних із роботою в системі Science Index, звертайтесь, будь ласка, до служби підтримки:

Вводиться поняття поліноміальної генеричної зведеності алгоритмічних проблем, яке зберігає властивість розв'язності проблеми для багатьох входів і має властивість транзитивності і рефлексивності. Доводиться, що класична проблема здійсненності булевих формул є повною щодо цієї зведеності в генеричному аналогу класу NP.

'> Входить у РІНЦ ® : так

'> Цитування в РІНЦ ® : 1

'> Входить у ядро ​​РІНЦ ® : так

'> Цитування з ядра РІНЦ ® : 0

'> норм. цитування за журналом:

'> Імпакт-фактор журналу в РІНЦ: 0,417

'> норм. цитованість за напрямом: 4,363

'> Дециль у рейтингу за напрямом: 1

'> Тематичний напрямок: Mathematics

'> Включено у збірки: 2

'> Всього відгуків: 0

Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of algoritm on typical (all all) inputs and ignores the rest of inputs. Багато класичних невизначених або твердих algoritmických проблем стає сприятливим в generic case. Але вони є загальним важливими проблемами. У цій статті ми встановлюємо висновок про generic polynomial reducibility algorithmic problems, which preserve the property of polynomial decidability of the problematic for all inputs and has properties of transitivity. Це вказує на те, що класична надійність проблеми Boolean formulas is complete with respect to this generic reducibility in the generic analog class NP.

---