Re: NP or not NP


[Форум Rossia.org] [Ответы и комментарии] [Написать ответ]


Отправлено Рубен Герр 22:55:42 12/03/1999
в ответ на: Re (1):!..., отправлено Felix 19:39:03 12/03/1999

 
> Рубен, я не знаю какое у Вас образование, но непонятно каким это образом Вы путаете задачу и методы ее решения. 
Опять пустословный лозунг! 
 
 
> Далее, NP-сложной называется задача, для решения которой не существует другого метода, кроме как полного перебора вариантов. 
Если ограничиться только этой формулировкой, NP-полных задач на практике не бывает вообще. Обычно подразумевается все же не перебор ВСЕХ вариантов (ибо их ВСЕГДА бесконечное число на практике), а всех осмысленных вариантов. Все равно этих вариантов много, и все равно их число растет факториально. Именно в этом смысле я и использовал данный термин. Впрочем, не я один. 
 
> Поскольку Вы сами признали, что при рыночной экономике,  задача оптимизации экономических отношений  _решается_, то NP-сложной эту задачу считать, очевидно, нельзя. 
Поскольку читать чужие реплики, не являющиеся непосредственным ответом на Ваши, вам, вероятно, сейчас некогда, процитирую ответ Тошика на мою исходную: 
>Простите, что сейчас нет времени отвечать подробнее, но существует теория фирмы Коуза (нобелевская-91).  
>    Которая говорит, что размер фирмы ограничивается маржиналистскими соображениями: фирма имеет тот размер, при котором организация одной дополнительной транзакции внутри фирмы стоит столько же, сколько 
покупка ее результата на внешнем рынке.  
>    Поэтому, то, что фирмы не растут бесконечно (следует учитывать не только захват одного рынка, но расширение спектра продуктов и услуг), говорит о большей относительной эффективности рыночного 
управления.  
>  
 
NP-полные задачи неразрешимыми в принципе не являются, они становятся неразрешимыми, начиная с некоторого уровня. Причем сложность их нарастает нелинейно, а факториально по отношению к числу параметров.  
Удельная цена единичной транзакции внутри фирмы с ростом самой фирмы увеличивается, а не остается постоянной (см. выше). Именно поэтому есть пределы роста фирм. (Противодействие этому капиталисты тоже нашли — они холдинги придумали, но это реплика в сторону.) Кстати, соотнесите, пожалуйста, Ваше высказывание о рассмотрении государства как единого предприятия c результатами нобелевского лауреата... 
 
> Эта задача [распараллеливания алгоритмов] вполне успешно описана теоретически, и вполне успешно решается на практике в тех же системах управления производством. 
А вот тут я позволю себе высказывание в Вашем стиле: бред какой!! 
 
С уважением


Ответы и комментарии:


[Форум Rossia.org] [Начало] [Написать ответ]