[Форум Rossia.org] [Ответы и комментарии] [Написать ответ]
Отправлено
Felix 15:47:09 13/03/1999
в ответ на:
Re: NP or not NP, отправлено
Рубен Герр 22:55:42 12/03/1999
Рубен, Вы хоть чуть-чуть пытаетесь понять логику моих рассуждений? Или Вы считаете себя априори правым и не утруждаетесь? >> Рубен, я не знаю какое у Вас образование, но непонятно каким это образом Вы путаете задачу и методы ее решения. > Опять пустословный лозунг! Это Вы пустословием занялись, отрезав кусочек от моего утверждения. Я объяснил Вам, в чем состоит путаница в Ваших рассуждениях. Человек я неленивый, так что еще раз и подробнее: Есть задача оптимизация экономических отношений в рамках экономики страны. Есть методы ее решения 'рыночное регулирование' и 'планирование экономики'. С точки зрения ПМ в первом случае адекватный мат.метод стохастическое моделирование (на практике моделью служит сама реальность), во втором предполагается заранее произвести некие аналитические расчеты, а потом проводить их результаты в жизнь. Естественно, эти расчеты имеют свою сложность, но то, что им _обязательно_ соответствует решение NP-сложной задачи это Ваша выдумка, нелепость которой очевидна каждому, знакомому с этим делом на практике. Я опять таки приводил объяснения почему это так, и рассказывал каким образом можно уходить от этой NP-сложности и слышал в ответ, что мол плохо работает. Аргумент совершенно бессмысленный по двум причинам. Во-первых, я обсуждаю NP-сложность задачи, а не эффективность тех или иных методов ее решения. Во-вторых, для того, чтобы говорить о том, плохо или хорошо работает планирование экономики, надо иметь некий критерий для оценки результатов. Разговоры о том, что конкретно Вам или жителям колхоза Багряное или сантехнику дяде Васе при плановой экономике было плохо в качестве критерия не принимаются. Никто не сказал, что конечным результатом развития экономики должно быть обязательно Ваше личное благополучие, а не, например, благополучие тех людей, которым при плановой экономике было хорошо, а сейчас плохо. Как бы Вам не было обидно. >> Далее, NP-сложной называется задача, для решения которой не существует другого метода, кроме как полного перебора вариантов. > Если ограничиться только этой формулировкой, NP-полных задач на практике не бывает вообще. Собственно, прикладные методы в математике и предназаначены для получения 'локально оптимальных' решений в тех случаях, где чисто аналитический способ решения задачи нереален по ресурсам или в принципе не возможен. Т.е. с точки зрения формальной математической теории задача может быть NP-сложной или вовсе не разрешимой, а на практике ее успешно решают. Именно поэтому я и назвал Ваши рассуждения про NP-сложность планирования экономики фигней. В прикладных системах, конечно тоже иногда используется лобовой перебор вариантов, не очень масштабно и он никогда не являлся основным методом решения задач. >Обычно подразумевается все же не перебор ВСЕХ вариантов (ибо их ВСЕГДА бесконечное число на практике), NP-сложная задача задача не имеющая никаких способов решения более быстрых, чем последовательный перебор вариантов. По определению. Вы можете подразумевать что угодно, но у термина есть конкретное значение и Вы этот термин употребляете неправильно. > а всех осмысленных вариантов. А что есть 'осмысленный вариант'? Это вариант, профильтрованный через некии эвристики так что Вы поиздевались сначала над тем, что я их упомянул в качестве метода урезки дерева решений, а потом сами пришли к тому же. >Все равно этих вариантов много, Да. > и все равно их число растет факториально. Это абсолютно голословное и ничем не доказанное заявление. >Именно в этом смысле я и использовал данный термин. Впрочем, не я один. Неправильное употребление термина это Ваша личная проблема, и проблема тех, кто его употребляет неправильно вместе с нами. Факториальный рост числа вариантов никак не связан с NP-сложностью задачи. Более того, факториальный рост числа вариантов отнюдь не подразумевает факториальный рост времени решения задачи. Количество вариантов и время решения задачи в общем случае вообще не связаны. > >> Поскольку Вы сами признали, что при рыночной экономике, задача оптимизации экономических отношений _решается_, то NP-сложной эту задачу считать, очевидно, нельзя. > Поскольку читать чужие реплики, не являющиеся непосредственным ответом на Ваши, вам, вероятно, сейчас некогда, процитирую ответ Тошика на мою исходную: >>Простите, что сейчас нет времени отвечать подробнее, но существует теория фирмы Коуза (нобелевская-91). эту я прочел. >> Которая говорит, что размер фирмы ограничивается маржиналистскими соображениями: фирма имеет тот размер, при котором организация одной дополнительной транзакции внутри фирмы стоит столько же, сколько > покупка ее результата на внешнем рынке. >> Поэтому, то, что фирмы не растут бесконечно (следует учитывать не только захват одного рынка, но расширение спектра продуктов и услуг), говорит о большей относительной эффективности рыночного > управления. по очевиденым причинам это неправда. фирмы в США росли неограниченно, до тех пор, пока их не остановили антимонопольными законами. И вообще теория Коуза может применяться только в высоконкурентой экономике, где предложение по всем позициям превышает спрос. А на практике всегда идет борьба за ресурсы, число которых ограниченно и рост фирмы может остановить именно нехватка ресурсов, захваченных конкруентами. > NP-полные задачи неразрешимыми в принципе не являются, они становятся неразрешимыми, начиная с некоторого уровня. Причем сложность их нарастает нелинейно, а факториально по отношению к числу параметров. > Удельная цена единичной транзакции внутри фирмы с ростом самой фирмы увеличивается, а не остается постоянной (см. выше). Я не понимаю, почему см.выше. Ваше рассуждение абсолютно голословно стоимость внутрифирменной транзакции меняется в зависимости от эффективности управления, а системы управления производством в своей работе полный перебор вариантов не используют. Более того, если бы то, что Вы пишите было правдой, мы бы наблюдали рост стоимости транзакций внутри фирмы, прямо связанный с ее размерами. Чего опять-таки не видно. > Именно поэтому есть пределы роста фирм. Именно поэтому Ваши рассуждения никак не связаны с пределами роста фирм. > (Противодействие этому капиталисты тоже нашли — они холдинги придумали, но это реплика в сторону.) Кстати, соотнесите, пожалуйста, Ваше высказывание о рассмотрении государства как единого предприятия c результатами нобелевского лауреата... Отнес. См. выше. >> Эта задача [распараллеливания алгоритмов] вполне успешно описана теоретически, и вполне успешно решается на практике в тех же системах управления производством. > А вот тут я позволю себе высказывание в Вашем стиле: бред какой!! Ну и позволяйте, сколько угодно. Только не надо выдирать мои слова из контекста там не [распараллеливания алгоритмов] должно было стоять а [распараллеливания алгоритмов экономического планирования] А мы тут эти системы управления производством между делом в промышленность потихоньку внедряем...
Ответы и комментарии: