Belonging to the class P of the satisfability problem for a propositional formula with a given value of its bracket characteristic

Authors

  • Nikolay K. Kosovskiy St.Petersburg State University, Universitetskaya nab., 7/9, St.Petersburg, 199034, Russian Federation;
  • Tatiana M. Kosovskaya St.Petersburg State University, Universitetskaya nab., 7/9, St.Petersburg, 199034, Russian Federation;

Abstract

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.

Keywords:

propositional formula, satisfability of propositional formula, class P

Downloads

Download data is not yet available.

Downloads

Published

2014-05-01

How to Cite

Kosovskiy, N. K., & Kosovskaya, T. M. (2014). Belonging to the class P of the satisfability problem for a propositional formula with a given value of its bracket characteristic. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 1(2), 192–195. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/11042

Issue

Vol. 1 No. 2 (2014)

Section

Mathematics

License

Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.