Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования
Показано, що для задач про покриття (які відрізняються однією позицією матриці обмежень) не існує поліноміальних k-ймовірнісних процедур аналізу стійкості (k∊{ZPP, RP}) при k≠ NP. It is shown that the set covering problems (which differ in one position of the constraint matrix) have no -probabilist...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2015 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/207910 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования / Н.В. Лищук // Проблемы управления и информатики. — 2015. — № 3. — С. 54-58. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860234488718557184 |
|---|---|
| author | Лищук, Н.В. |
| author_facet | Лищук, Н.В. |
| citation_txt | Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования / Н.В. Лищук // Проблемы управления и информатики. — 2015. — № 3. — С. 54-58. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Показано, що для задач про покриття (які відрізняються однією позицією матриці обмежень) не існує поліноміальних k-ймовірнісних процедур аналізу стійкості (k∊{ZPP, RP}) при k≠ NP.
It is shown that the set covering problems (which differ in one position of the constraint matrix) have no -probabilistic polynomial procedures for sensitivity analysis (k∊{ZPP, RP}) if k≠ NP.
|
| first_indexed | 2025-12-07T18:22:38Z |
| format | Article |
| fulltext |
© Н.В. ЛИЩУК, 2015
54 ISSN 0572-2691
УДК 519.854
Н.В. Лищук
СЛОЖНОСТЬ ВЕРОЯТНОСТНЫХ ПРОЦЕДУР
АНАЛИЗА УСТОЙЧИВОСТИ ЦЕЛОЧИСЛЕННЫХ
ЗАДАЧ БУЛЕВА ПРОГРАММИРОВАНИЯ
Введение
Для задач дискретного программирования анализ устойчивости сводится к
определению таких изменений параметров (коэффициентов) исходной задачи, при
которых оптимальное решение остается без изменений [1]. Эффективность и про-
стота — основные черты случайных алгоритмов, что часто делает рандомизацию
полезной для решения сложных задач в разнообразных приложениях. В частно-
сти, в [2] рандомизация используется для исследования постоптимального анали-
за задач дискретной оптимизации. Поскольку понятия постоптимального анализа
и анализа устойчивости в некотором смысле взаимосвязаны, возникает идея ис-
пользовать результаты работ [2–4] для исследования сложности вероятностных
процедур анализа устойчивости целочисленных задач булева программирования.
Полиномиальные вероятностные алгоритмы
В дальнейшем не будем проводить различия между проблемами распознава-
ния свойств, поиска и оптимизации, поскольку для NP-полных задач они вычис-
лительно эквивалентны (этот вопрос подробно исследуется в [5]).
Дадим некоторые необходимые в дальнейшем понятия и определения [5–7].
Сначала определим ВМТ — вероятностную машину Тьюринга (МТ). Суще-
ствует два подхода к определению ВМТ, приведем их.
Определение 1. Вероятностная машина Тьюринга аналогична недетермини-
рованной машине Тьюринга, только вместо недетерминированного перехода в два
состояния машина выбирает один из вариантов с равной вероятностью.
Определение 2. Вероятностная машина Тьюринга представляет собой детермини-
рованную машину Тьюринга (ДМТ), имеющую дополнительно источник случайных
битов, любое число которых, например, она может заказать и загрузить на отдельную
ленту и использовать в вычислениях обычным для МТ образом. Оба определения —
1(online ВМТ) и 2(offline ВМТ) — эквивалентны. Более того, они вполне соответству-
ют обычному компьютеру, к которому подключен внешний генератор случайных по-
следовательностей на основе случайных физических процессов.
Определение 3. Пусть A — случайный алгоритм, который допускает ответ
«?» (не знаю). Будем говорить, что A — алгоритм Лас Вегас для функции F , если
для каждого входа x
,
2
1
)]()([ xFxAP (1)
,
2
1
)]()([1)?"")([ xFxAPxAP (2)
условие (2) исключает неправильный ответ, так как дается правильный ответ или «?».
Если )(xA — полиномиальная ВМТ, то соответствующий класс сложности — .ZPP
Определение 4. Случайный алгоритм A называется алгоритмом Лас Вегас,
вычисляюшим функцию F, если для произвольного входа x .1)]()([ xFxAP
Модели из определений 3 и 4 эквивалентны в том смысле, что каждую из них
можно свести к другой.
Определение 5. Пусть A — случайный алгоритм и ),( L — проблема распо-
знавания свойств ( — алфавит, L — язык). Будем говорить, что A — алгоритм
Международный научно-технический журнал
«Проблемы управления и информатики», 2015, № 3 55
Монте-Карло с односторонней ошибкой (1MC), если
2
1
]1)([ xAP для каждого
Lx и 1]0)([ xAP для каждого .Lx Если A — полиномиальная ВМТ, то
соответствующий класс сложности — RP.
Справедливы следующие включения классов сложности проблем [5–7]:
NPRPZPPP (3)
Об эффективном вероятностном анализе устойчивости задач
булева программирования
Введем формализацию понятия эффективного вероятностного анализа ус-
тойчивости для задач булева программирования.
Пусть — некоторая NP-трудная оптимизационная задача (возможно, и NP -
полная), I — экземпляр задачи . Каждому экземпляру I задачи поставлено в
соответствие множество )}({ I экземпляров задачи . Анализ устойчивости для па-
ры )})({)(,( IIII дает ответ на вопрос: будет ли оптимальное решение экземпляра
I )})(opt({ I оптимальным решением экземпляра I задачи с )}({ I ? Введем поня-
тие -эффективного ( — один из классов ), RPZPP устойчивого сведения экземп-
ляров задачи ).( ans
Функцию )(xf с областью определения D будем называть
тождественной в области определения, если xxf )( для произвольного .Dx
Определение 6. Будем говорить, что экземпляр I' -эффективно
}),{( RPZPP устойчиво сводится к экземпляру ,I если существует такая
полиномиально вычислимая на ВМТ из класса , тождественная в области опре-
деления функция ),(f что )),(()'( IoptfIopt обозначение .ans I'I При этом
сложностью анализа устойчивости для пары ),( I'I называется сложность, число
тактов ВМТ для вычисления ).(f
Согласно определению 6 введены сведения ., RP
ans
ZPP
ans
Замечание 1. Введенное понятие устойчивости соответствует устойчивости
по функционалу, рассмотренному в [8].
Будем говорить, что функция )(nf полиномиального роста )),(poly)(( nnf
если для некоторой константы ))1(( Occ при достаточно больших n выполняет-
ся .)( cnnf
Определение 7. Задачу (распознавания свойств, поиска, оптимизации) будем
называть -полиноминально разрешимой }),,{( RPZPP если существует по-
линомиальная ВМТ из класса , которая дает (точное) решение задачи.
Рассмотрим задачу )(P булева программирования вида
)},...,,()(min{ 1 nxxfxf
,}1,0{ nnBGx
а также семейство }{ IP задач булева программирования :)( IP
)},...,,()(min{ 1 nxxfxf
,}1,0{ nn
I BGx
где }...,,,{ 21 qIIII — экземпляры семейства задач },{ IP ),(poly nq среди
qII ...,,1 есть экземпляр, который соответствует задаче (P) (т.е. ).: GGj
jI
56 ISSN 0572-2691
Для произвольных :, nByx yx тогда и только тогда, когда
,ii yx ....,,1 ni
Теорема 1. Если одновременно выполняются условия:
1) существует полиномиальная ВМТ из класса }),{( RPZPP для опреде-
ления допустимого решения x задачи (Р) такого, что не существует
;',',' xxxxGx
2) для произвольного допустимого решения *x задачи (Р) существуєт
экземпляр pI семейства )( IP такой, что *x — оптимальное решение относительно
;
pIG
3) ,...21 qansansans III то задача (Р) — -полиноминально разрешимая.
Доказательство полностью аналогично доказательству теоремы 3 из [2].
Сложность вероятностного анализа устойчивости
задачи о покрытии множествами
Задачу о покрытии множествами будем рассматривать в постановке (задача
:),( cA
,)()(min
1
AQxxcxf
n
i
ii
,...,,1,1)(
1
n
j
jij
n mixaBxAQ
;...,,1;...,,1},{,}1,0{ njmiaAB ij
nn ),( nmA — булева матрица );( nm
....,,1,0 nici
Для булевых ),( nm -матриц }{}{ ijij bBaA введем метрику B(A
.
,
ji
ijij ba
Пусть }...,,{},...,,1{},...,,1{ 11 kiiKnNmM — некоторая выборка из N
объемом ).,1( mknkk Точка n
n B )...,,( 1 такая, что 1 j при
,1Kj 0 j при ,\ 1KNj а ni
n
ii B )...,,( 1 такая, что 0,1 i
j
i
i
при .ij Опишем класс }{ A булевых ),( nm -матриц };{ ijAA }{ AA тогда
и только тогда, когда матрица A не содержит одинаковых и нулевых строк и,
кроме этого, выполняются условия:
1) у матрицы A есть подматрица 1A ;...
1
ki
i
2) у матрицы A есть подматрица ),\}({ 1
2 NjKMiaA ij такая, что для
произвольного
1
,1\ 1
Kj
ijaKMi остальные элементы у
2A произвольны.
Пусть
n
n Bxxx )...,,( **
1
*
такой, что ,1... **
1
kii xx остальные координа-
ты вектора *x равны 0, }.{*
AA
Международный научно-технический журнал
«Проблемы управления и информатики», 2015, № 3 57
Лемма 1 [3]. Пусть *x — (единственное) оптимальное решение экземпля-
ра I задачи ).,( * cA
Пусть *x — оптимальное решение экземпляра I задачи о покрытии ),( cA
и A — такая, что .1),( AA
Можно ли за полиномиальное время определить, что *x остается оптималь-
ным решением задачи ?),( cA В связи с этим пусть )),,(( *xcA'Check — про-
цедура, которая определяет оптимальное решение *x задачи ),,( cA' исходя из
оптимального решения *x задачи ).,( cA Если эта процедура соответствует
сводимости }),,{( RPZPPans то будем ее называть -вероятностной поли-
номиальной процедурой анализа устойчивости.
Теорема 2. Пусть }.,{ RPZPP Если ,NP то существует экземпляр I
задачи ),,( cA что для )),,'(( *xcACheck не существует -вероятностной по-
линомиальной процедуры анализа устойчивости.
Доказательство проведем для случая RP (для случая ZPP аналогич-
но). Воспользуемся идеями из [2]. Допустим, что для произвольного экземпля-
ра I задачи ),,( cA для )),,(( *xcACheck существует RP-вероятностная по-
линомиальная процедура анализа устойчивости.
Пусть Alg — произвольный (приближенный) полиномиальный алгоритм из
класса RP для решения произвольного ),( cAI и n
n Bxxx )...,,( **
1
* такой,
что ,1... **
1
kii xx остальные координаты вектора *x равны 0, есть результат
работы алгоритма Alg на .I Пусть }{*
AA — матрица, соответствующая ,*x
в силу леммы 1 алгоритм Alg для экземпляра
*I (экземпляр ),( cA с матрицей
)*AA даст точное решение задачи и п. 1 теоремы 1 выполнен.
Пусть для произвольной булевой ),( nm -матрицы A )(AT -преобразование
матрицы A с заменой произвольного ее одного элемента 0 на 1, или 1 на 0 Запи-
шем, что ),(ATA' если после применения к A преобразования T получилась
матрица A' (ясно, что ).1),( A'A
Произвольную матрицу A можно получить из матрицы ,*A применяя не бо-
лее, чем nm преобразований :T
,...21
* AAAAA k
TTTT
(4)
где ,1),(),( *
1
*
1 AAATA
;1...,,1,1),(),( 11 kiAAATA iiii
,2nnmk
т.е. выполнен п. 2) теоремы 1.
Применяя к последовательности (4) RP -вероятностную полиномиальную
процедуру анализа устойчивости )),,(( *xcA'Check k раз )( 2nnmk полу-
чим, что для произвольного экземпляра I задачи ),( cA существует последова-
тельность ,*I 121 ,...,,, kk IIII экземпляров, причем
RP
ansI *
,... 121 k
RP
ansk
RP
ans
RP
ans
RP
ans IIII
где ,...),,(),,(),,( 2312
*
1 cAIcAIcAI
58 ISSN 0572-2691
.),,(),,( 11 AAcAIcAI kkkkk
Выполнен п. 3 теоремы 1. Отсюда следует, что задача ),( cA RP -полино-
миально разрешима, т.е. принадлежит классу .RP Показано, что .RPNP Отсю-
да, так как NPRP ((3)), получим .NPRP
Теорема доказана.
Замечание 2. Результат, подобный теореме 2, имеет место для задачи о ранце.
Заключение
Анализ устойчивости задач дискретной оптимизации в разных постановках
рассматривался в работах [1, 4, 8–10]. Например, в [4] установлено, что решение
обобщенно близких задач о ранце является NP-трудным. Данная работа показыва-
ет, что для задач о покрытии (которые отличаются в одной позиции матрицы ог-
раничений) не существует полиномиальных -вероятностных процедур анализа
устойчивости })),{( RPZPP при .NP
Н.В. Ліщук
СКЛАДНІСТЬ ЙМОВІРНІСНИХ ПРОЦЕДУР
АНАЛІЗУ СТІЙКОСТІ ЦІЛОЧИСЛОВИХ ЗАДАЧ
БУЛЕВОГО ПРОГРАМУВАННЯ
Показано, що для задач про покриття (які відрізняються однією позицією мат-
риці обмежень) не існує поліноміальних -ймовірнісних процедур аналізу
стійкості }),{( RPZPP при .NP
N.V. Lishchuk
THE COMPLEXITY OF PROBABILISTIC SENSITIVITY
ANALYSIS PROCEDURES FOR INTEGRAL BOOLEAN
PROGRAMMING PROBLEMS
It is shown that the set covering problems (which differ in one position of the con-
straint matrix) have no -probabilistic polynomial procedures for sensitivity analysis
}),{( RPZPP if .NP
1. Fernandez-Baca D., Benkatachalam B. Sensitivity analysis in combinatorial optimization //
handbook of approximation algorithms and metaheuristics (ed. T. Guzalez). — 2007. — Chap-
man&Hall / CRC Computer and Information Science Series. — P. 30-1–30-29.
2. Михайлюк В.А. Подход к оценке сложности вероятностных процедур постоптимального
анализа дискретных задач оптимизации // Кибернетика и системный анализ. — 2012. — 48,
№ 6. — С. 3–10.
3. Михайлюк В.А. Общий подход к оценке сложности постоптимального анализа дискретных
задач оптимизации // Кибернетика и системный анализ. — 2010. — 46, № 2. — С. 134–141.
4. Михайлюк В.A., Лищук Н.В. Анализ устойчивости задачи о ранце: один отрицательный ре-
зультат // Кибернетика и системный анализ. — 2013. — 49, № 2. — С. 48–51.
5. Goldreich O. Computational complexity. A conceptual perspective. — Cambridge University
Press, 2008. — 606 p.
6. Hromkovich J. Design and analysis of randomized algorithms. Introduction to design para-
digms. — Berlin; Heidelberg: Springer-Verlag, 2005. — 279 p.
7. Кузюрин Н.Н., Фомин С.А. Сложность вычислений и анализ алгоритмов. — М.: МФТИ,
2007. — 312 с.
8. Леонтьев В.К., Мамутов К.Х. Устойчивость решений в задачах линейного булева программи-
рования // Журн. вычисл. математики и матем. физики. — 1988. — 28, № 10. — С. 1475–1481.
9. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимиза-
ции. — Киев : Наук. думка, 1985. — 210 с.
10. Сергиенко И.В., Филоненко Н.В. Решение некоторых задач устойчивости в целочисленном
линейном программировании // Докл. АН УССР. Сер. А. — 1982. — № 6. — С. 79–82.
Получено 31.03.2015
|
| id | nasplib_isofts_kiev_ua-123456789-207910 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T18:22:38Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Лищук, Н.В. 2025-10-15T18:50:45Z 2015 Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования / Н.В. Лищук // Проблемы управления и информатики. — 2015. — № 3. — С. 54-58. — Бібліогр.: 10 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207910 519.854 10.1615/JAutomatInfScien.v47.i5.70 Показано, що для задач про покриття (які відрізняються однією позицією матриці обмежень) не існує поліноміальних k-ймовірнісних процедур аналізу стійкості (k∊{ZPP, RP}) при k≠ NP. It is shown that the set covering problems (which differ in one position of the constraint matrix) have no -probabilistic polynomial procedures for sensitivity analysis (k∊{ZPP, RP}) if k≠ NP. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования Складність ймовірнісних процедур аналізу стійкості цілочислових задач булевого програмування The complexity of probabilistic sensitivity analysis procedures for integral Boolean programming problems Article published earlier |
| spellingShingle | Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования Лищук, Н.В. Оптимальное управление и методы оптимизации |
| title | Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования |
| title_alt | Складність ймовірнісних процедур аналізу стійкості цілочислових задач булевого програмування The complexity of probabilistic sensitivity analysis procedures for integral Boolean programming problems |
| title_full | Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования |
| title_fullStr | Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования |
| title_full_unstemmed | Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования |
| title_short | Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования |
| title_sort | сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207910 |
| work_keys_str_mv | AT liŝuknv složnostʹveroâtnostnyhproceduranalizaustoičivosticeločislennyhzadačbulevaprogrammirovaniâ AT liŝuknv skladnístʹimovírnísnihproceduranalízustíikostícíločislovihzadačbulevogoprogramuvannâ AT liŝuknv thecomplexityofprobabilisticsensitivityanalysisproceduresforintegralbooleanprogrammingproblems |