Относно общата NP-пълнота на проблема за изпълнимостбулеви формули

За всички въпроси, свързани с работата в системата Science Index, моля, свържете се с поддръжката:

Въвежда се концепцията за полиномиална обща редуцируемост на алгоритмични проблеми, която запазва свойството разрешимост на проблема за почти всички входове и има свойството транзитивност и рефлексивност. Доказано е, че класическият проблем за изпълнимост за булеви формули е пълен по отношение на тази редуцируемост в общия аналог на класа NP.

'> Включено в RSCI ® : да

'> Цитирания в RSCI ® : 1

'> Включено в ядрото RSCI®: да

'> Цитати от основния RSCI®: 0

'> норма. цитат в списанието:

'> Импакт фактор на журнала в RSCI: 0,417

'> норма. цитиране на посока: 4363

'> Децил в класирането по посока: 1

'> Тематично направление: Математика

'> Представено в колекции: 2

'> Общо отзиви: 0

Подходът на общ случай към алгоритмичните проблеми беше предложен от Miasnikov, Kapovich, Schupp и Shpilrain през 2003 г. Този подход изучава поведението на алгоритъм върху типични (почти всички) входове и игнорира останалите входове. Много класически неразрешими или трудни алгоритмични проблеми стават осъществими в общия случай. Но има общи трудни проблеми. В тази статия ние въвеждаме понятието за общи алгоритмични проблеми с полиномна редуцируемост, които запазват свойството на полиномна разрешимост на проблема за почти всички входове и имат свойството транзитивност. Доказано е, че класическият проблем за изпълнимост на булеви формули е завършен по отношение на тази обща редуцируемост в общия аналог на клас NP.

---