NP-completeness conditions for some types of systems of linear Diophantine dis-comparisons consistency checking

Authors

  • Nikolay K. Kosovskii St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;
  • Tatyana M. Kosovskaya St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;
  • Nikolay N. Kosovskii St. Petersburg State University, Universitetskaya nab., 7-9, St. Petersburg, 199034, Russian Federation;

DOI:

https://doi.org/10.21638/11701/spbu01.2016.104

Abstract

-

Downloads

Download data is not yet available.
 

References

Литература

1. Кривий С.Л. Лiнiйнi дiофантовi обмеження та їх застосування. Видавничий дiм «Букрек». 2015. 224 с.

2. Быкова В.В. Программирование задач на графах ограниченной древовидной ширины // Программные продукты и системы. Т. 4, №96, 2011. С. 101-106.

3. Косовская Т.М., Косовский Н.К. О числе шагов получения булевого решения у полиномиальных сравнений и у систем из них // Вестник С-Петерб. ун-та. Сер. 1. 2007. Вып. 3. С. 82-90.

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

5. Stockmeyer L.J., Meyer A.R. Word problems requiring exponential time // Proc. 5th Ann. ICM Symp. on Theory of Computing. Association of Computing Machinery. New York, 1973. P. 1-9.

6. Shafer T.J. The complexity of satisfiability problems // Proc. 10th Ann. ACM Symp. on Theory of Computing. Association of Computing Machinery. New York, 1978. P. 216-226.

References

1. Krivyi S. L., Linear Diophantine equations and their decisions (Publishing House “Bukrek”, 2015, 224 p.) [in Ukrainian].

2. Bykova V.V., “Programming of problems for a bounded tree-type width graph”, Program products and systems 4(96), 101–106 (2011) [in Russian].

3. Kosovskii N.K., Kosovskaya T.M., “The Number of Steps for Construction of a Boolean Solution to Polynomial Congruences and Systems of Polynomial Congruences”, Vestnik St. Petersburg University: Mathematics 40(3), 218–223 (Allerton Press. Inc., 2007).

4. Garey M.R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NPCompleteness (Freeman, New York, 1979).

5. Stockmeyer L. J., Meyer A.R., “Word problems requiring exponential time”, Proc. 5th Ann. ICM Symp. on Theory of Computing (1–9) (Association of Computing Machinery, New York, 1973).

6. Shafer T. J., “The complexity of satisfiability problems”, Proc. 10th Ann. ACM Symp. on Theory of Computing (216–226) (Association of Computing Machinery, New York, 1978).

Downloads

Published

2020-10-19

How to Cite

Kosovskii, N. K., Kosovskaya, T. M., & Kosovskii, N. N. (2020). NP-completeness conditions for some types of systems of linear Diophantine dis-comparisons consistency checking. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 3(1), 1. https://doi.org/10.21638/11701/spbu01.2016.104

Issue

Vol. 3 No. 1 (2016)

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.