Standard

О ЧИСЛЕ ШАГОВ ПОЛУЧЕНИЯ БУЛЕВОГО РЕШЕНИЯ У ПОЛИНОМИАЛЬНЫХ СРАВНЕНИЙ И У СИСТЕМ ИЗ НИХ. / Косовский, Н. К.; Косовская, Т. М.

In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, No. 3, 2007, p. 84-90.

Research output: Contribution to journal › Article › peer-review

Harvard

Косовский, НК & Косовская, ТМ 2007, 'О ЧИСЛЕ ШАГОВ ПОЛУЧЕНИЯ БУЛЕВОГО РЕШЕНИЯ У ПОЛИНОМИАЛЬНЫХ СРАВНЕНИЙ И У СИСТЕМ ИЗ НИХ', ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, no. 3, pp. 84-90. <http://elibrary.ru/item.asp?id=11481414>

APA

Косовский, Н. К., & Косовская, Т. М. (2007). О ЧИСЛЕ ШАГОВ ПОЛУЧЕНИЯ БУЛЕВОГО РЕШЕНИЯ У ПОЛИНОМИАЛЬНЫХ СРАВНЕНИЙ И У СИСТЕМ ИЗ НИХ. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, (3), 84-90. http://elibrary.ru/item.asp?id=11481414

Vancouver

Косовский НК, Косовская ТМ. О ЧИСЛЕ ШАГОВ ПОЛУЧЕНИЯ БУЛЕВОГО РЕШЕНИЯ У ПОЛИНОМИАЛЬНЫХ СРАВНЕНИЙ И У СИСТЕМ ИЗ НИХ. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ. 2007;(3):84-90.

Author

Косовский, Н. К. ; Косовская, Т. М. / О ЧИСЛЕ ШАГОВ ПОЛУЧЕНИЯ БУЛЕВОГО РЕШЕНИЯ У ПОЛИНОМИАЛЬНЫХ СРАВНЕНИЙ И У СИСТЕМ ИЗ НИХ. In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ. 2007 ; No. 3. pp. 84-90.

BibTeX

@article{edceca447dbb490c93f7a0225b7f6df4,
title = "О ЧИСЛЕ ШАГОВ ПОЛУЧЕНИЯ БУЛЕВОГО РЕШЕНИЯ У ПОЛИНОМИАЛЬНЫХ СРАВНЕНИЙ И У СИСТЕМ ИЗ НИХ",
abstract = "Формулируются пары похожих по формулировке задач, связанных с решением в {0,1}* сравнений (и несравнений) арифметических выражений по числовому модулю, относительно одной из которых доказывается ее полиномиальность по времени, а другая обобщает ее как подзадачу. Доказывается NP-полнота обобщенной задачи, которая при простом модуле традиционными математическими символьными преобразованиями сводится к первой.By means of fixing a parameter some NP-complete problems, connected with the solving of comparisons (and non-comparisons) of arithmetical terms by prime modulo, are decomposed as a union of an infinite set of problems for which polynomial-time algorithms are constructed.",
author = "Косовский, {Н. К.} and Косовская, {Т. М.}",
year = "2007",
language = "русский",
pages = "84--90",
journal = "ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ",
issn = "1025-3106",
publisher = "Издательство Санкт-Петербургского университета",
number = "3",

}

RIS

TY - JOUR

T1 - О ЧИСЛЕ ШАГОВ ПОЛУЧЕНИЯ БУЛЕВОГО РЕШЕНИЯ У ПОЛИНОМИАЛЬНЫХ СРАВНЕНИЙ И У СИСТЕМ ИЗ НИХ

AU - Косовский, Н. К.

AU - Косовская, Т. М.

PY - 2007

Y1 - 2007

N2 - Формулируются пары похожих по формулировке задач, связанных с решением в {0,1}* сравнений (и несравнений) арифметических выражений по числовому модулю, относительно одной из которых доказывается ее полиномиальность по времени, а другая обобщает ее как подзадачу. Доказывается NP-полнота обобщенной задачи, которая при простом модуле традиционными математическими символьными преобразованиями сводится к первой.By means of fixing a parameter some NP-complete problems, connected with the solving of comparisons (and non-comparisons) of arithmetical terms by prime modulo, are decomposed as a union of an infinite set of problems for which polynomial-time algorithms are constructed.

AB - Формулируются пары похожих по формулировке задач, связанных с решением в {0,1}* сравнений (и несравнений) арифметических выражений по числовому модулю, относительно одной из которых доказывается ее полиномиальность по времени, а другая обобщает ее как подзадачу. Доказывается NP-полнота обобщенной задачи, которая при простом модуле традиционными математическими символьными преобразованиями сводится к первой.By means of fixing a parameter some NP-complete problems, connected with the solving of comparisons (and non-comparisons) of arithmetical terms by prime modulo, are decomposed as a union of an infinite set of problems for which polynomial-time algorithms are constructed.

M3 - статья

SP - 84

EP - 90

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 3

ER -

ID: 5161437