Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений

Авторы

  • Николай Кириллович Косовский Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9
  • Татьяна Матвеевна Косовская Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9
  • Николай Николаевич Косовский Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9

DOI:

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

Аннотация

-

Скачивания

Данные скачивания пока недоступны.
 

Библиографические ссылки

Литература

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).

Загрузки

Опубликован

19.10.2020

Как цитировать

Косовский, Н. К., Косовская, Т. М., & Косовский, Н. Н. (2020). Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизсравнений. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 3(1), 1. https://doi.org/10.21638/11701/spbu01.2016.104

Выпуск

Том 3 № 1 (2016)

Раздел

Математика

Лицензия

Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.

Наиболее читаемые статьи этого автора (авторов)