Принадлежность классу P задачи проверки выполнимости пропозициональной формулы с заданным значением её скобочной характеристики

Аннотация

The notion of bracket characteristic of a propositional formula in the basis of negation, multiple conjunctions, multiple disjunctions and multiple equivalences is introduced. It is proved that the satisfability problem for a propositional formula with any previously given bracket characteristic belongs to the class P. So, we have a new hierarchical decomposition of the initial NP-complete problem into sub-problems from the class P. In this case every problem of the hierarchy permits an infnite set of input data.

Ключевые слова:

propositional formula, satisfability of propositional formula, class P