компьютерное, сложность

[avva]

Теоретический анализ сложности программ и алгоритмов сам по себе вполне самодостаточен с математической точки зрения. То, что такой-то алгоритм работает такое-то время, например O(n) или O(n²) (т.е. асимптотически пропорционально количеству входных данных или пропорционально квадрату количества), является строгим математическим фактом.

Однако практическое применение этих теоретических знаний опирается, по-моему, на определенные допущения, которые далеко не столь математически точны, как теоретические факты. Под "практическим применением" я имею в виду то, что мы, например, склонны предпочесть алгоритм O(n) эквивалентному алгоритму O(n²) - конечно, это простейший случай, и на практике все бывает намного сложнее, плюс есть вопрос затрат на память, а не только затрат времени, но суть ясна. Есть математические факты, и есть их интерпретации в виде предпочтения тех или иных алгоритмов, попыток улучшить, прагматичных советов и указаний, итд. итп.

Эти предпочтения, советы итд. опираются на некоторые неявные допущения. Допущения эти, во-первых, иногда неверны, а во-вторых, что более важно, нет (по-моему) удовлетворительного объяснения тому, что обычно они верны. Отсутствие такого объяснения - своего рода дыра в теоретическом фасаде анализа программ и алгоритмов.

Вот два примера.

Во-первых, мы обычно пользуемся оценками для худшего случая (worst-case complexity). Если разные значения входных данных приводят к разным затратам времени (или памяти) алгоритмом, мы выбираем худшие результаты (для данного фиксированного количества входных данных), и их используем для оценки функции затрат в общем случае. Однако худший случай и общий случай - весьма разные вещи. На практике может оказаться, что худший случай случается достаточно редко, а в типичном случае алгоритм ведет себя намного лучше, чем утверждает наша пессимистичная оценка.

Известный пример - алгоритм quicksort. Он выполняется в худшем случае за время O(n²), а в среднем или типичном случае - за O(nlogn). Есть алгоритмы сортировки, которые всегда выполняются за O(nlogn), и в худшем случае тоже, т.е. теоретически они как бы лучше, чем quicksort, но на практике часто оказывается, что quicksort реально быстрее.

Но интересно не то, что есть пример того, как теоретическая основа приводит к неверной интерпретации. Интересно то, что это происходит так редко! Quicksort - известное исключение, но таких исключений мало; обычно сложность худшего случая хорошо отражает "практическую" пользу от алгоритма. Почему? Это не обязано априори быть так. Априори я не вижу причин, почему в огромном количестве самых обычных алгоритмов не может быть небольшого количества очень плохих случаев, как в quicksort, которые бы "искажали статистику". Но на практике это обычно не так, и мы пользуемся этим в качестве неявного допущения. Есть ли объяснение этому?

Кстати, почему мы вообще обычно пользуемся оценкой сложности по худшему случаю? Как это сложилось? Есть ли в этом выборе какой-то культурный смысл, может ли он нам сказать что-то о культуре поведения и мышления, создавшей цифровую цивилизацию? Могло ли другое общество изначально пользоваться намного более часто другими видами оценок? (конечно, я знаю, что и мы часто пользуемся другими видами оценок, например среднего случая, но все же оценка по худшему варианту преобладает).

Второй пример - само понятие асимптотической сложности. Не вполне ясно, почему оно вообще имеет какое-то отношение к окружающей нас действительно, где, грубо говоря, размеры всех входных данных и результатов ограничены на практике какой-то константой, скажем, 10³⁵. Математика говорит нам, что асимптотическая оценка, вообще говоря, ничего не значит в случае "небольших" значений, где "небольшое" значит "меньшее сколь угодно большой заранее зафиксированной постоянной". Асимптотика проявляется только в стремлении к бесконечности. Почему она оказывается полезной в реальном мире?

Можно сформулировать этот вопрос более конкретно. Скажем, есть два алгоритма, один O(2ⁿ), экспоненциальный, другой O(n), линейный. Мы "знаем", что первый намного намного хуже второго. Но конечно же может быть так, что при первом стоит очень очень очень малый множитель, а при втором - очень очень очень большой, так что на практике, для всех размеров данных, которыми мы можем оперировать в реальном мире, первый будет намного намного лучше второго.

Но этого не происходит, за редкими исключениями. Почему? Есть ли у нас удовлетворительный ответ на этот вопрос?

Comments

[akusasik.livejournal.com]

Так есть нормальные теоретичекие подходы к этому. Вместо "worst case complexity", если алгоритм бегает н раз нужно считать "amortized complexity". Expeted runtime of quicksort быстрее expected runtime of determenistic sorting algorithms that run in nlogn.

Совершенно формальные способы обосновывать и то, и другое.

Только этими вещами программисты не пользуются, потому что там математика чуть-чуть бывает нетривиальная.

[ex-ex-annut.livejournal.com]

Вы ничего не путаете?
Amortized complexity имеет мало отношения к выполнению quicksort n раз, если все эти n раз он запускается на различных массивах
"программисты" очень интенсивно пользуются и онлайновыми алгоритмами, и даже анализом этих алгоритмов

[ygam.livejournal.com]

Заранее не знаешь, что за заподло тебе будет подсовывать примеры задач. Может, тебе дадут сортировать как раз те массивы, на которых быстрая сортировка квадратична.

[prosto-tak.livejournal.com]

Именно так объяснял это дело Леонид Левин на курсе алгоритмов. Он говорил, что нужно считать, что входные данные подсовывают враги, и именно исходя из этого анализировать алгоритмы. Что иногда не так уж далеко от истины, например, если мы имеем дело с Denial of Service attacks.

[roza.livejournal.com]

Шёпотом: а таги кто ставить будет?

[andreev.livejournal.com]

Оценка по худшему варианту применительно к задачам массового обслуживания действительно говорит о культуре, породившей - не пропустить цель.

[vinopivets.livejournal.com]

+1. Оценка по наихудшему - историческое явление. Есть нормальные оценки и для средних времен, и для времен вычислений в условиях ограниченной памяти, но программисты туда, видимо, теперь не ходят - математически много сложнее.

[waxtep.livejournal.com]

По-первому мне кажется зависит от приложения - если алгоритм используется регулярно и должен гарантированно давать результат "не позднее, чем к ланчу", то именно оценка по худшему случаю важна. Он рано или поздно приключится, и ланч остынет. А если приложение не такое, то у человека, возможно, неприятие риска повышенное, диагноз по переписке готов ! :-)

Почему исключений среди алгоритмов мало, хммм. Ну мне единственное что в голову приходит, это родственный вопрос -каких последовательностей "больше" - сходящихся равномерно, или же неравномерно ? Я, правда, и на него не отвечу, прочно забыто.

По-второму я бы снова переформулировал, да запутался в формулировках, уф. Здоровенных бессмысленных чисел быть не должно, я лично в это верю, скажем так. [Что никак не отрицает наличия асимптотически лучших алгоритмов с практически худшими свойствами на реальных диапазонах входных данных - такого-то хватало.]

[waxtep.livejournal.com]

>>Здоровенных бессмысленных

Здоровенных осмысленных конечно, запуталсо окончательно.

[michk.livejournal.com]

Оценка по худшему случаю - очевидно, из желания гарантировать результат (т.е. время).
По поводу квадратичного алгоритма с малым фактором и линейного с большим - довольно нелегко представить себе 2 таких алгоритма, делающих одно и то же, с фактором, скажем, 1000, не говоря уже о 1000000. Соответственно, в задачах, где размер исходных не сильно ограничен, квадратичный будет хуже.

[sillykong.livejournal.com]

Выбор наихудшей оценки на практике вполне объясним на интуитивном уровне.
Забиваясь на худший враиант, мы обеспечиваем некий гарантированный "запас прочности". Т.е. наш алгоритм точно будет работать не медленнее некоей определённой величины и в этом мы можем быть уверены на 100%. А если мы в критичном куске кода забьёмся на статистику, говорящую о том, что "с вероятностью 99% на практике всё работает быстро, но есть 1% случаев, когда будет медленно", мы лишаем себя запаса прочности. Т.е. если в случае понижения производительности у нас возникает исключительная ситуация, то мы обязаны забиваться на худший расклад. Это является следствием стремления человека делать всё с запасом.
Шоб ничё, если чё.
Это если говорить о бытовом уровне понимания.
Т.е. это простейшая логика, которая объясняет такую традицию в оценке.
Или Вы не об этом?

[eterevsky.livejournal.com]

Поставленные вопросы таки рассматриваются в теории сложности.

Во-первых, что касается QuickSort, обычно используется его вариант, когда разбиение ведётся по случайному элементу. Это -- вероятностный алгоритм, имеющий сложность именно O(n log n). Далее, есть вариант QuickSort'а, который будет работать за O(n log n) в худшем случае. Но им никто не пользуется, так как он становится куда медленнее любого вменяемого алгоритма.

Во-вторых, рассмотрим, например, алгоритмы умножения длинных чисел. Умножение «столбиком» работает за O(n²), но именно его стоит использовать в случае относительно небольших чисел. Немного более сложный алгоритм работает за время, если я не ошибаюсь, O(n^(log 4/log 3)). Наконец, наилучший известный на сей день алгоритм, основанный на дискретном преобразовании Фурье, работает за O(n log(n) log(log(n))). Но им пользуются только когда приходится осуществлять вычислений с совсем длинными числами, скажем от сотни тысяч знаков, а такая надобность всё-таки встречается нечасто. :)

Наконец, упомяну ещё тему. Некоторые используемые алгоритмы выдают результат с некоторой вероятностью ошибки. При этом, за счёт повторения эта вероятность может быть сколь угодно уменьшена. Таковы, например, широко используемые алгоритмы определения простоты числа. В данный момент большая работа ведётся по дерандомизации (устранению случайности) в данных алгоритмах. В прошлом году, например, был наконец найден детерменированный полиномиальный (от длины числа) алгоритм для проверки его на простоту. Тем не менее, эти усилия имеют, главным образом, теоретическую ценность, так как сложность вычислений в таких алгоритмах значительно выше.

[nevsky.livejournal.com]

В прошлом году, например, был наконец найден детерменированный полиномиальный (от длины числа) алгоритм для проверки его на простоту.
Ссылку не дадите?

[dmpogo.livejournal.com]

Ne znaju, w nauchnyh prilozhenijah dovol'no chasta situacija kogda kak raz prefaktory wazhny, i asimptoticheskoe powedenie mozhet ne dostigat'sja w real'nyh zadachah.

[syarzhuk.livejournal.com]

что при первом стоит очень очень очень малый фактор
Наверное, всё-таки множитель.

[al-zatv.livejournal.com]

factor - множитель.

[al-zatv.livejournal.com]

O(2^n) хуже (в большинстве случаев) независимо от фактора. Почему? Потому что при росте n неприлично растёт. Поэтому, вот что мы имеем при анализе применения алгоритма.

Пусть есть два алгоритма - A1 с O(n), и A2 с O(n^2), работающий на БД.

1)Пусть в БД 100 записей. Пусть A1 работает 10 секунд, А2 - 2 секунды. Вроде бы, лучше А2.
(условно, у первого t=n*0.1, у второго 2*(n/100)^2
2)В БД стало 200 записей. A1 работает 20 секунд, А2 - 8 секунд. Вроде бы, лучше А2.
3)В БД стало 300 записей. A1 работает 30 секунд, А2 - 18 секунд. Вроде бы, лучше А2.
4)В БД стало 10 000 записей. A1 работает 1000 секунд, А2 - 20 000 секунд. Вроде бы, лучше А2.
4)В БД стало 100 000 записей. A1 работает 10000 секунд, А2 - 2 миллиона секунд. Вроде бы, лучше
А2.

И это ведь не зависит от фактора. А уж если брать не n^2 а 2^n, то можно быть уверенным: чуть станет больше данных, как он "свалится". Так что в данном случае теория очень практична:)

[ex-ex-annut.livejournal.com]

просто дело в том, что в задачах бд множители всегда близкие к единице

[sply.livejournal.com]

Все это основывается на одном, в общем-то, неверном допущении, что оценка по худшему случаю действительно является стандартом. Что совсем не так. В статьях, где описываются или сравниваются алгоритмы, практически никогда не бывает сравнений только по худшему случаю, разве что в нехороших статьях. Оценка затрат памяти тоже бывает в O и ее тоже нередко приводят.

А вот вполне обычный пример http://en.wikipedia.org/wiki/String_search , правда, без памяти.

[netch]

Если посмотреть что Кнут пишет про обменную сортировку Хоара, сиречь quicksort, видно, что для последовательностей короче 20 элементов он применяет не её, а вполне себе квадратичный метод вставок. Понятно, что конкретное число 20 - специфика его MIX-1009, но пример показателен.

И сложность действительно можно мерять по-разному. Например, как матожидание от сложности для каждого конкретного случая, и тогда для quicksort получится всё то же O(n log n). Но с худшим случаем тут получилась особая история: он слишком вероятный и показательный - и, что ещё более важно, недетектируемый за меньшие затраты чем сам алгоритм. Поэтому - спецмеры. А если бы детектирование того, что пошли куда-то не туда, занимало бы время значительно меньшее чем сама сортировка - был бы применён какой-то другой метод. Хотя это и так, похоже, возможно: если при разделении подотрезка получились слишком неравные длины - сменить медианное значение или применить другой метод разделения (например, ван Эмдена).

[eterevsky.livejournal.com]

А как определить, что получились «слишком неравные длины»?

[vasja-iz-aa.livejournal.com]

Вы забыли упомянуть плату памятью за скорость.

[dmpogo.livejournal.com]

+1

[ex-ex-annut.livejournal.com]

кстати, эта странность проявляется и в смежной области
Например, расматривать задачу Set Cover
которая полна в NP
есть очень быстрый и эффективный жадный алгоритм, но у которого логарифимический аппрокс фактор даже для ограниченного случая (размера множества и частоты элемента)
есть "хорошие алгоритмы", которые всегда решают задачу с постоянным фактором (в ограниченном случае)
но если построить случайную задачу то жадный алгоритм аппроксимирует гораздо лучше и считает гораздо быстрее

[ex-ex-annut.livejournal.com]

таким примеров в аппрокс алгоритмах для NP полных задач много

[relf.livejournal.com]

другой известный пример - симплекс метод, который в худшем случае экспоненциален, но на практике очень эффективен.

[oblomov-jerusal.livejournal.com]

вы меня опередили.

[allasm.livejournal.com]

"Но конечно же может быть так, что при первом стоит очень очень очень малый множитель, а при втором - очень очень очень большой... Но этого не происходит, за редкими исключениями. Почему?"

Ну, сравнивая даже не n^2 и 2^n, а n^2 и n^3, даже при очень маленьких n, скажем 100, разница между ^2 и ^3 - 100 раз. Взяться такой большой константе, судя по всему, неоткуда.

Я не знаю, какие алгоритмы, достойные анализа, часто используются в индустрии (или "на практике"), но вспоминая тот же quicksort или поиск, или простые граф-алгоритмы (тот же matching), которые я хоть когда-то на практике использовал, там почти никогда констант больше 2-5-10 нет.

Совсем от балды - наверняка я что-то упускаю на бегу - константа может взяться от, скажем, "отсортируем это так, а это едак - итого x2", или "возьмём три копии", "пройдем два раза, туда, сюда", и так далее. Видно, у нас или задачи слишком простые, чтоб константы возникли большие, или наш чловеческий мозг не может придумать таких алгоритмов, где б большая константа пригодилась.

Причем, скорее всего, задачи - специально наверняка можно придумать задачу ассимптотически более быстро решаемую только с офигенной константой.

---

"Кстати, почему мы вообще обычно пользуемся оценкой сложности по худшему случаю? Как это сложилось?"

Видно, на практике, подождать на секунду дольше каждый раз, но не ждать пол года в худшем случае работает лучше - логика тут вполне есть. Опять же, иногда ж таки используются алгоритмы более быстрые "в среднем".

[faceted-jacinth.livejournal.com]

По поводу "оценки по худшему случаю" вроде уже всё сказали, нам как правило нужно гарантированное время получения результата.

> Но конечно же может быть так, что при первом стоит очень очень очень малый множитель, а
> при втором - очень очень очень большой, так что на практике, для всех размеров данных,
> которыми мы можем оперировать в реальном мире, первый будет намного намного лучше второго.

Вот это как раз довольно просто на вид. Во-первых, "очень малых множителей" не бывает, они все больше единицы. Разве что если мы параллелить пытаемся, но это совершенно другой случай (хотя тоже интересный, но там как бы сразу понятно, что оценивать нужно Специальным Образом). Значит, нам нужен "очень, очень, очень большой" множитель, а это тоже довольно странная вещь, если вспомнить, откуда, собственно, множители берутся. Мы ж количество операций считаем. Допустим, у нас есть какой-то алгоритм, который на каждом условном шаге использует миллион операций. Причём это число не зависит от параметра, иначе мы бы были обязаны внести его в скобки. Но это, наверное, означает то, что все эти операции как бы присутствуют в более или менее явном виде в условном "коде" алгоритма, не правда ли? Причём они все довольно разные. А нам нравятся короткие алгормы, алгоритмы, которые мы можем понять.

Конечно, можно попытаться представить алгоритм, которому нужно на каждом шаге считать определитель матрицы 100х100, но это число, 100, почему-то оказывается естественным образом фиксированным для любого n. Странная, должно быть, штука.

Да, а ещё, когда говорят об асимптотической оценке, как правило подразумевают намного более узкий смысл, чем математический, точнее даже не подразумевают, а он сам логичным образом проявляется. Алгоритмы естественным образом разбиваются на куски, типа этот кусок работает за константное время, этот - за логарифмическое, этот - за линейное етс, в качестве финальной оценки берётся наибольшее, всё оставшееся заметается в множитель. Не все алгоритмы, конечно, а те, которые нравятся людям. Поэтому математически легальная ситуация с "ассимптотическим стремлением", когда, скажем, при n < 10^100 время работы алгоритма колеблется случайно от 1 до 10^100, а дальше вдруг становится почти строго линейно пропорциональным n, в реальности очень неестественна.



Так что из всего этого я для себя вынес единственный по-настоящему интересный вопрос: очень похоже, что людям "нравится" специфический класс алгоритмов, которые разбиваются на куски так, как я сказал, ну и всё такое. Что-то вроде ограниченных рекурсивных функций из GEB. А непонятные алгоритмы (вроде вот такой эзотерической штуки) людям наоборот не нравятся. Так вот, можно ли формализовать "привлекательность" алгоритма в виде языка, допускающего только "привлекательные алгоритмы", насколько такой язык будет соответствовать современным ЯП, и какие именно проблемы окажутся в нём нерешаемыми?

Worst, Average, Expected, Smoothed, parametrized, etc complexities

[(Anonymous)]

A major reason for looking at the worst case complexity is that it is something we can compute. Average case complexity is a great notion, but it not well defined. For example in sorting, will we be looking at all possible n! permutations and taking the average over those? In more complex algorithms, this gets even hairier.

Someone up there brought up the simplex method as a great example of a provably exponential time algorithm that is widely used. In fact this has been a topic of a lot of study, and culminated in the notion of "smoothed" complexity by Spielman & Teng ( see: http://www-math.mit.edu/~spielman/SmoothedAnalysis/). This is a mathematically well defined interpolation between worst & average case complexities. Formally, take an instance X, add some random noise \sigma, and then look at the worst case expected (over \sigma) complexity. In other words, if the bad cases are very specific and brittle, the smoothed complexity of an algorithm will likely be much lower than its worst case. The simplex method is one such algorithm: the monumental result of spielman and teng is that the smoothed complexity of simplex is polynomial.

Randomization also yields interesting interpretations. There're some algorithms where the expected running time is exponential, but really, in a vast majority of the cases the run time is polynomial. In theoretical cs papers, you often see that something works with "high probability," usually meaning w/ prob 1 - 1/n. For example, we can prove that randomized quicksort works in O(n log n) time w.h.p. and not just in expectation.

just my 2 cents.

[os80.livejournal.com]

>Кстати, почему мы вообще обычно пользуемся оценкой сложности по худшему случаю? Как это сложилось?
Мне кажется, что мы пользуемся всеми оценками, а потом принимаем решение в зависимости от контекста. В большинстве случаев мы хотим быть уверены на 100 процентов, что программа закончит работу за определённое время. Не замечали, что нас раздражают алгоритмы, которые будут работать неизвестно сколько?
Теперь по QuickSort. В этом случае вероятность медленной работы алгоритма очень мала. Меньше, чем вероятность перегорания компьютера.

философия

[illyn.livejournal.com]

Не замечали, что нас раздражают алгоритмы, которые будут работать неизвестно сколько?

Вот, кстати! Жизнь один из таких. Причём и сам неизвестен.

[savenkov.livejournal.com]

Но интересно не то, что есть пример того, как теоретическая основа приводит к неверной интерпретации. Интересно то, что это происходит так редко! Quicksort - известное исключение, но таких исключений мало; обычно сложность худшего случая хорошо отражает "практическую" пользу от алгоритма.

Это не так. Возможно, в определённых областях единственным примером таких алгоритмов является quicksort, но есть масса других областей со своими алгоритмами, и там ситуация такая же. В качестве первого примера можно привести алгоритмы, используемые для анализа и преобразования текстов программ (коль скоро я достаточно близко знаком с данной областью). В типичном случае структура графа программы достаточно проста, и алгоритмы работают, на самом деле, быстро. Однако worst-case complexity для них может считаться для произвольного ориентированного графа без кратных ребер (особенно если рпименяется классический графовый алгоритм вроде транзитивного замыкания).

Ситуация, которая происходит в таком случае (а равно и в случае quicksort) решается, на мой взгляд, достаточно просто. Нужно сформулировать для входных данных алгоритма достаточное условие "типичного случая", при соблюдении которого либо будет получаться реальная оценка времени работы данного алгоритма, либо модно будет использовать другой алгоритм, у которого worst-case complexity выше, однако для данных условий она минимальна.

Такой подход хорош и тем, что если проверка этого условия будет проста относительно сложности самого алгоритма (что, впрочем, не всегда возможно), то это позволит для конкретных входных данных подобрать подходящий алгоритм.

Однако есть и более общий пример таких "пародоксальных" алгоритмов. Возьмите любую NP-трудную задачу и эвристический алгоритм её решения. Вы получите абсолютно ту же ситуацию, что и с quicksort. В общем случае алгоритм работает экспоненциальное время, а на том "типичном случае" входных данных, для которого разрабатывалась эвристика -- иногда даже линейное.


Кстати, почему мы вообще обычно пользуемся оценкой сложности по худшему случаю? Как это сложилось? Есть ли в этом выборе какой-то культурный смысл, может ли он нам сказать что-то о культуре поведения и мышления, создавшей цифровую цивилизацию?


Это объясняется очень просто. БОльшая часть исследований, посвящённых оценке сложности и времени работы вычислительной системы инспирирована задачами, связанными с работой ПО в режиме реального времени (в основном, для военных систем). Это та область, для которой вопросы сложности являются критическими. И критическим является именно время работы худшего случая. Почему — думаю, понятно.


Можно сформулировать этот вопрос более конкретно. Скажем, есть два алгоритма, один O(2n), экспоненциальный, другой O(n), линейный. Мы "знаем", что первый намного намного хуже второго. Но конечно же может быть так, что при первом стоит очень очень очень малый множитель, а при втором - очень очень очень большой, так что на практике, для всех размеров данных, которыми мы можем оперировать в реальном мире, первый будет намного намного лучше второго.

Но этого не происходит, за редкими исключениями. Почему? Есть ли у нас удовлетворительный ответ на этот вопрос?


М-мм... Откуда такой вывод?
Для любой области, где есть несколько принципиально различных алгоритмов, можно в простанстве значений входных данных построить области, в каждой из которых один из алгоритмов эффективнее. Соответственно, в данной области применять этот алгоритм. Никакого максималима здесь не требуется — вряд ли в абсолютном большинстве случаев будет эффективнее работать один из них. Например, если идёт работа со списком, в котором нужно что-то искать, то можно использовать либо список, либо кучу. На небольшом количестве данных список будет гораздо быстрее, однако на большом ситуация изменится. Хотя константы там разные, да. Ну да вы это и сами знаете.

Э...

[savenkov.livejournal.com]

модно читать как можно :-)

[oblomov-jerusal.livejournal.com]

Классический пример это алгоритм симплекс для линейного программирования. Для большинства вариантов известно, что 'worst case экспоненциальный, тем не менее алгоритм широко применяется и на практике работает почти линейно.

[glukanat.livejournal.com]

Возможно причина совпадения среднего и худшего в следующем.
Есть известный парадокс бесколнечного случайного графа. Оказывается, что он всего лишь один. Он связен, в нем максимальная клика включает подавляющее число вершин и так далее.
Все асимптотики на графах так или иначе сводятся к одному этому графу. Что в худщем случае, что в среднем.

[ex-ex-annut.livejournal.com]

тут очень важно сказать какаю модель случайно вы расматривается (как задается пространство событий)
так как все предыдущее верно только для эрдошевских случайных графов

[timur0.livejournal.com]

Оценка по худшему случаю - единственно возможная при рассмотрении NP-полных задач, т.к. при моделировании интересующей нас задачи в NP-полной может получиться совсем редкий случай; более того, может оказаться, что при моделировании какого-либо типа задач в выбранной NP-полной все или большинство начальных данных будут являться как раз этими редкими худшими случаями (см. выше про полные графы). Если взять иную оценку сложности задачи (среднюю по возможным начальным данным, к примеру), то уже нельзя будет легко сформулировать понятие NP-полноты - надо будет доказывать, что начальные данные при моделировании также распределяться равномерно, что, вообще говоря, неверно.

[ex-ex-annut.livejournal.com]

интересно, а нет ли какой оценки "потности" сложных случаев
известно, что не существует NP-полных sparse sets (Mahaney, 1982)
а нет ли хотя бы такой оценки сложных случаев?

[ex-ex-annut.livejournal.com]

интересно, а нет ли какой оценки "потности" сложных случаев
известно, что не существует NP-полных sparse sets (Mahaney, 1982)
а нет ли хотя бы такой оценки сложных случаев?

[ex-ex-annut.livejournal.com]

оппс
это был комментарий, не туда ушел