Вопрос по P = NP

Там вообще речь шла о нахождении одного такого сайта. Если нашли один, выходим из вычислений, независимо от остальных.

Но это не столь важно, там суть в том, чтобы понять разницу между вычислениями на ДМТ и НМТ, поэтому лучше взять что-нибудь унифицированное.

ну так докажи общее. хоть как нибудь.

Это к чему твой высер был?

ну так исправляй свое непонимание.

Это ты сейчас на публику работаешь?

Если ты доказал общее, зачем тебе тогда вообще индукция?

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

ну так докажи общее.

нет. ты уже понял, что признать то, что «тушенка — человек» тебе мешает непонимание логики, а не ее воображаемые «большие проблемы». теперь фикси его.

Но это не столь важно, там суть в том, чтобы понять разницу между вычислениями на ДМТ и НМТ, поэтому лучше взять что-нибудь унифицированное.

Ну на НМТ будет сложность вообще О(1), так как можно начать сразу с подходящего сайта. А на ДМТ будет О(n) или что-то около, так как может оказаться, что такой сайт всего один и он последний в списке.

Сложность полиномиальная

тихо ты, у нас тут пока что тушенка — человек. рановато пришел.

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

К примеру, утверждение «завтра пойдет снег или завтра не пойдет снег» тоже является истиным утверждением, это тавтология. Слабоват ты еще пока в логике, но стремление похвально.

Это ты не понял.

А формальная логика, кстати, сама по себе имеет большие проблемы, настолько большие, что кто-нибудь будет вправе назвать ее бесполезной игрушкой.
К примеру, утверждение, «все люди состоят из мяса и костей -> тушенка состоит из мяса и костей --> тушенка — это человек» — вычисляется, похоже в истину:)

Он не вычисляется в истину, потому что из «A включено в C, B включено в C» не следует «B включено в C». A — множество людей, B — множество тушенки, C — множество объектов, состоящих из мяса, ты — унылее с каждым часом.

из «(...) B включено в C» не следует «B включено в C»

Вот именно поэтому и не рекомендуется спорить с шизофрениками.

Ух ты! Невероятно! Пророк! Посмотри сразу таблицу истинности импликации, надо спасать тушенку.

блин, надо же так было опечататься, он теперь меня вообще съест.

fix:

К примеру, утверждение, «все люди состоят из мяса и костей -> тушенка состоит из мяса и костей --> тушенка — это человек» — вычисляется, похоже в истину:)

из «A включено в C, B включено в C» не следует «B включено в A».

импликации

Причем тут импликация?

Вы про что-то свое, женское. Речь шла о силлогизмах. Это высказывания, вида 2 факта — вывод. Например, факт1: Сократ человек. факт2: люди смертны. Вывод: Сократ смертен. Тут нет никаких включений.

теперь меня вообще съест.

Да съесть тебя легко, вот мозг твой включить — задача нетривиальная. Я ниасилю.

А тебя на шизофрении фикс, определенно. Это уже какой тред по счету с такой симптоматикой?

Только лишь в этом треде уже 2 раза, как минимум. Палишься, чувак. Тебя это беспокоит по жизни?

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

Какие множества? Ты о чем? Это был пример неправильного силлогизма. Ты бредишь штоле? И да, ты так и не ответил, какое отношение высказывание «завтра пойдет снег или завтра не пойдет снег» имеет к импликации? Или ты просто для красного словца, как всегда, незнакомое словечко ввернул?

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

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

твоя эта фраза никакого отношения ни к чему не имеет, ты ее ввернул для красного словца

Как я и сказал ранее имеет отношение, непосредственное, к логике, и она является тавтологией.

в том числе и к импликации.

Тогда зачем же ты посоветовал обратится к таблице

Посмотри сразу таблицу истинности импликации

?

при чем тут множества?

Если в смысле проверки этого силлогизма, то некоторое отношение имеют, да и то не множества как таковые, с математической точки зрения, а включения. Вот пример

Пример неправильного силлогизма:

Все тигры (М) – млекопитающие (Р). Все тигры (М) – хищники (S).

Все хищники (S) – млекопитающие (Р). Отношения между терминами данного силлогизма могут быть представлены двояко, как это показано на рисунке. И в первом, и во втором случаях все М (тигры) входят в объем Р (млекопитающие) и все М входят также в объем S (хищники). Это соответствует информации, содержащейся в двух посылках силлогизма. Но отношение между объемами Р и S может быть двояким. Охватывая М, объем S может полностью входить в объем Р или объем S может лишь пересекаться с объемом Р. В первом случае можно было бы сделать общее заключение «Все хищники – млекопитающие», но во втором случае правомерно только частное заключение «Некоторые хищники – млекопитающие». Информации, позволяющей сделать выбор между этими двумя вариантами, в посылках не содержится. Значит, мы не вправе делать общее заключение. Силлогизм не является правильным.

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

Отсюда по идее, должно вытекать простое следствие, P = NP, разве не так? Ведь NP — это ни что иное, как алгоритм выполняемый на недетерминированной МТ. В чем подвох?

Извиняюсь, если не понял вопрос, но P - это подмножество всех задач, решаемых детерминированной МТ за полиномиальное время, NP - подможество всех задач, чьи решения проверяются за полиномиальное время. Считается, что подмножества не равны: P<>NP. Если бы они были равны (P==NP), то есть, если бы из того, что решение проверяется за полиномиальное время, следовало бы, что существует решение за полиномиальное время, то у криптографии были бы проблемы, но почему это вытекает из твоего примера неясно.

https://en.wikipedia.org/wiki/P_versus_NP_problem#P_.3D_NP

А в чем разница, принципиальная, между решением и проверкой? Например, есть задача из «n шариков выбрать красный», путем перебора. И «проверить, есть ли в n шариков красный». Эти 2 задачи совпадают, тут проверка эквивалентна решению, и в обоих случаях перебор. Это просто игра слов. И при чем тут тогда недетерминированная машина тьюринга?

P является подмножеством NP, т.е. есть задачи, где проверка одинаковой сложности с решением. Но обратное не доказано, поэтому считается, что NP шире P. Задачи с решениями проверяемыми за полиномиальное время, но не решаемые за полиномиальное время называются NP-complete

Ух ты! Невероятно! Пророк! Посмотри сразу таблицу истинности импликации

Это называется «дизъюнкция»

Абсолютно ясно, что НМТ нам тут ни какого выигрыша не даст. Допустим, мы на первом шаге начали проверку не с первого, а, (недетерминированно) со второго сайта.

Внимательно пойми, что такое недетерминированная машина тьюринга.

Идиоты отписавшиеся в теме ранее - идиоты.

Например, есть задача из «n шариков выбрать красный», путем перебора. И «проверить, есть ли в n шариков красный».

Если уж использовать твои аналогии, то задачи приблизительно такие:

1) Есть ли срези этих n шариков красный? 2) Правда ли, что этот шарик красного цвета?

Понятно, что вторая задача уж не сложнее первой. Интуитивно кажется, что вторая существенно проще, но не доказано.

Интуитивно кажется, что вторая существенно проще, но не доказано.

Стоп. А как ты можешь доказать это, ведь тут не хватает информации. Допустим предикат isRed содержит в себе сопоставление образца с семью цветами, а шариков для передобора — всего 3. Тогда, вопреки твоему утверждению, вторая задача «сложней» первой. Либо — наоборот. Это напрямую зависит от входных данных и от предиката.

Я считаю, что этому треду нужно больше треша и угара, поэтому предлагаю пообсуждать следующий интересный факт:

Всем известно, что задача «существует ли в графе гамильтонов цикл?» — NP-полная задача. Но про другую очень похожую задачу, а именно «не существует ли в графе гамильтонов цикл?» не известно, лежит ли она в NP вообще.

ЗЫ задачи отличаются тем, что если к первой ответ «Да», то ко второй — «Нет» и наоборот.

Стоп. А как ты можешь доказать это, ведь тут не хватает информации.

Я лишь продолжил твою аналогию. Тут нет утверждения, которое претендует на доказательство.

Допустим предикат isRed содержит в себе сопоставление образца с семью цветами, а шариков для передобора — всего 3. Тогда, вопреки твоему утверждению, вторая задача «сложней» первой. Либо — наоборот. Это напрямую зависит от входных данных и от предиката.

Почему сложнее? Первая задача решается троекратным выполнением второй задачи.

Первая задача решается троекратным выполнением второй задачи.

Нет. Для решения первой задачи тебе вторая может вообще не понадобится. Ты просто берешь в качестве образца красный шарик и решаешь ее путем сопоставления с этим шариком за 3 шага. А вторая тащит за собой 7 шагов.

Это похоже на бредятину какую-то. Ясно, что это эквивалентные задачи, тут простая инверсия.

Нет. Для решения первой задачи тебе вторая может вообще не понадобится. Ты просто берешь в качестве образца красный шарик и решаешь ее путем сопоставления с этим шариком за 3 шага. А вторая тащит за собой 7 шагов.

Если ты можешь решить первую задачу за три шага, то и вторую тоже можешь решить за три или даже меньше.

Понято, проверка решения второй задачи соответствует решению первой.
Ответ «да» или «нет» придется проверять перебором

Это похоже на бредятину какую-то. Ясно, что это эквивалентные задачи, тут простая инверсия.

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

то и вторую тоже можешь решить за три или даже меньше

Только при условии, что у нас не более 3-х или меньше возможных цветов.

Настолько неочевидно

В чем неочевидность? Возьмем снова аналогию с шарами. Допустим стоит задача, проверить, есть ли красный шар. Лучший случай - первым попадается красный, выходим. худший — попадается последним или нт вообще. Теперь берем обратное. Попадается первым — выходим — лучший случай, в худшем — гребем до конца. В чем разница? То же самое и с твоим.

Ответ «да» или «нет» придется проверять перебором

Ну так в любом случае все решается перебором. Для решения любой из задач нужна просто инверсия другой.

нет не в любом, и я вообще про гамильтонов цикл отвечал

Вообще не по тебе, но мне кажется твой алгоритм не оптимальным.

Я бы сначала проверил ВСЕ сайты на наличие и Васи, и Пети. И составил два списка - один все сайты с Васей, другой - все сайты с Петей (некоторые сайты могут оказаться в обоих списках).

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

Опять паленые таблетки получил?

Кстати, да, я немного ошибся. задача isRed решается в один шаг, в любом случае, это просто сопоставление. Я почему-то в голове держал что-то вроде whatColor. Получается, что неэквивалентность задач доказывается легко. Во втором случае, ты решаешь за один шаг, гарантированно. Во втором, предполагается, что шагов может быть более одного, соответственно и шагов >= 1. (>=1 не эквивалентно 1) В чем проблема?

Потому что если не требовать доказательство наличия, то мы будем считать, что существует всё, что только сможем придумать. Скажем, прямо сейчас над тобой висит летающий макаронный монстр, просто ты его не видишь. А по улице ходят невидимые единороги. А на орбите Солнца летают стаи чайников Рассела.

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

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

Не знаю, как будет в общем случае, но, очевидно, что если мы угадывает «пару» на первом шаге (лучший случай), то твоя версия проиграет. Дальше будет распределение по градации 2 шаг успех, 3 шаг успех и так далее. Твой алгоритм начнет выигрывать, возможно, где-то с середины, да и то не факт. Скорей всего вообще нет. Будет одинаково в общем случае. Если заморочиться, это в принципе, можно проверить:)

нет никаких удачных корректных экспериментов по его наблюдению

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