LINUX.ORG.RU

Вопрос по P = NP

 ,


0

2

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

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

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

В таком случае, что нам дает недетерминированная машина?

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

Буду благодарен за пояснения, но только без зауми.

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



Последнее исправление: aboutcard (всего исправлений: 2)
Ответ на: комментарий от KivApple

Весь процесс идёт сам

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

aboutcard
() автор топика
Ответ на: комментарий от aboutcard

Ну синтез аминокислот в имитации первичной атмосферы был вполне успешен, а остальное пока «катализировать» не научились. Сложновато ускорить модель на 9 порядков.

leave ★★★★★
()
Ответ на: комментарий от Waterlaz

не известно, лежит ли она в NP вообще.

Чего-то я не понимаю, вроде вычисление логического отрицания — это задача, выполняемая за константное время, следовательно сложность этих двух задач одинакова и они должны принадлежать одному классу, нет?

Xenius ★★★★★
()
Ответ на: комментарий от leave

Нет, по поводу рассела я уверен в том что говорю. Его теория чайника — бред сивой кобылы. Думай что хочешь.

aboutcard
() автор топика
Ответ на: комментарий от leave

Его основной фейл в том, что он притянул за уши логику туда, где чисто логически, абстрагируясь от *пристрастий* невозможно сказать, надо ли доказывать отсутствие чего-либо или наличие. Чайник тут не при чем, по большому счету. Его утверждение, абстрагируясь от пристрастий, можно переформулировать как «нужно доказывать наличие чего либо, а не отсутствие». Это утверждение, само по себе несотоятельно, естественно. Мы могли бы его на этом основании, попросить доказать *наличие отсутствия чайника*. А все остальное в этой истории — всего лишь пускание слюней.

aboutcard
() автор топика
Ответ на: комментарий от aboutcard

Но ведь это не имеет отношения к вопросу скорости вычислений.

Исключительно к нему и имеет.

Суммарно все шаги всех копий составят столько же тактов вычислений, сколько ДМТ.

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

Мы ведь распараллеливание тут не рассматриваем?

Как это не рассматриваем если возможность распараллеливания - это ЕДИНСТВЕННОЕ чем ДМТ отличается от НМТ? Без этого отличия ДМТ = НМТ, коненчо же.

anonymous
()

ЛОР ТОРТ!!!

3 (три) страницы вакханалии, и всего то для этого был необходим дурачок который из кустов прокричит P=NP!!!!.

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

itn ★★★
()
Ответ на: комментарий от Xenius

Чего-то я не понимаю, вроде вычисление логического отрицания — это задача, выполняемая за константное время, следовательно сложность этих двух задач одинакова и они должны принадлежать одному классу, нет?

К сожалению, нет. Есть даже класс задач, который называется coNP. Если вычисление f(x) принадлежит NP, то вычисление !f(x) принадлежит coNP.

Waterlaz ★★★★★
()
Ответ на: ЛОР ТОРТ!!! от itn

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

anonymous
()
Ответ на: комментарий от nguseff

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

t184256 ★★★★★
()
Ответ на: комментарий от t184256

А ты знаешь, что такое тест Тьюринга?

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

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

anonymous
()
Ответ на: комментарий от anonymous

Не пройдет, потому что и проходить не будет. Он вообще не способен что-то делать. Индуктивный вывод существует, тот высер  — не вывод. Тавтологии существуют, к теме не относятся, в логике называются как-то иначе. Тот «силлогизм» записывается через множества, а вы все — больные и не лечитесь.

Тебе что мало этого?

Абсолютно.

t184256 ★★★★★
()
Ответ на: комментарий от t184256

Индуктивный вывод существует

Фууу, успокоил.

в логике называются как-то иначе

да что ты говоришь, неужели? LДаже до википедии уже добраться не в состоянии?

https://ru.wikipedia.org/wiki/Тавтология_(логика)

Я че-то засомневался уже, а знаешь ли ты вообще, что такое логика.

anonymous
()
Ответ на: комментарий от KivApple

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

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

monk ★★★★★
()
Ответ на: комментарий от monk

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

Это как почему электрон атома не падает на ядро атома по неопределённости Гейзенберга.

ados ★★★★★
()
Последнее исправление: ados (всего исправлений: 1)
Ответ на: комментарий от KivApple

вантовая механика означает крах детерменизма.

Вообще-то не означает. Корреляционная интерпретация детерменистична.

anonymous
()
Ответ на: комментарий от monk

«Быть монахом» явно не генетически определяется, а геи - та самая флуктуация, которая происходит с определенной вероятностью. С-но, в популяции всегда будет в среднем определенная постоянная доля геев.

Ну и кроме того если ограничиться данными людей, то тысячи лет для эволюции - вообще не срок.

anonymous
()
Ответ на: комментарий от monk

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

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

ya-betmen ★★★★★
()
Ответ на: комментарий от KivApple

ночные беседы с анонiмусом заразны, ещё как

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

anonymous
()
Ответ на: комментарий от monk

В случае геев играет два фактора:

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

P. S.: Я не отстаиваю права геев. Нетрационная ориентация - генетическая болезнь, а выпячивать напоказ свои болячки или тем более гордиться ими - не культурно.

2) Это как раз та самая флуктуация. Небольшое количество их будет всегда, пока население земли составляет не сотни, а миллиарды людей. Банальная теория вероятности. Точно также, как из года в год рождается какое-то количество детей с врождёнными болезнями мало совместимыми с жизнью, хотя не так давно они умирали сразу после рождения, бороться за их жизнь научились только сейчас. То что популяция геев выше, чем могла бы быть, - вина пункта 1.

В случае монахов механизм передачи признака не генетический, а психологический (иначе говоря, «монах» - это фенотип, а не генотип). Конечно, можно предположить наличие генетического признака «устойчивость к религиозной пропаганде», но эволюция работает медленно, а человечество в том виде, в котором мы привыкли его видеть, существует всего лишь несколько тысяч лет. К тому же в монахи уходит слишком мало людей. Вот, скажем, стало бы добровольно монахами 50% населения планеты - в следующем поколении атеистов было бы уже заметно больше. А ещё «устойчивость к религиозной пропаганде» может оказать не только положительное влияние. Скажем, когда-то за такое могли и на костре сжечь, а тот, кто слепо верил, рисковал меньше.

Кстати, развитие медицины палка о двух концах. Спасая жизни людей с врождёнными генетическими заболеваниями, мы медленно но верно приближаем тот день, когда здоровые люди (то есть те, кто не нуждается в десятке операций после рождения) будут той самой «флуктуацией». Впрочем, это процесс достаточно медленный и если мы скоро научимся не только лечить заболевание, но и выпиливать его причину из генотипа пациента, то всё будет в лучших традициях эволюции, хотя и без человеческих жертв. Главное сделать коррекцию генотипа при лечении наследственной болезни строго обязательной.

KivApple ★★★★★
()
Последнее исправление: KivApple (всего исправлений: 2)
Ответ на: комментарий от anonymous

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

Как следствие, при гонении на геев, многие из них будут косить под натуралов. В том числе заводить детей, передавая им свои гены. Таким образом процент геев будет сильно выше ожидаемого через несколько поколений. Вот процент геев с принципами «моя ориентация это моё личное дело - я не пойду на поводу у общества и не буду притворяться» будет падать, да.

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

KivApple ★★★★★
()
Последнее исправление: KivApple (всего исправлений: 2)
Ответ на: комментарий от hfucker

И почему это она корреляционная?

Это ее оригинальное и более точное название, отражающее, собственно, смысл интерпретации. Многомировой стали называть чтобы было понятнее тупому быдлу.

Она малораспространенная, практически сдохла.

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

anonymous
()
Ответ на: комментарий от KivApple

цуконах...зашел в тему технического форума, почитать, что там aboutcard еще придумал, aboutcard уже забанили, а тут еще и про пидерастов. Нучозахерня? Стоило ли банить aboutcardа ради этого?

anonymous
()
Ответ на: комментарий от KivApple

Нетрационная ориентация - генетическая болезнь

Геи появляются там, где толпа мужиков долго живет вместе в ненормальных условиях. То есть это армия, тюрьмы и монастыри.

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

anonymous
()
Ответ на: комментарий от anonymous

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

hfucker
()
Ответ на: комментарий от anonymous

В цивилизованных странах большинство из этих проблем уже давно решены

Да, решены, причем кардинально. Там это просто объявлено нормой. Проблему можно решить 2 способами: решить ее, и объявить, что ее нет.

hfucker
()
Ответ на: комментарий от hfucker

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

hfucker
()
Ответ на: комментарий от hfucker

Проблему можно решить 2 способами: решить ее, и объявить, что ее нет.

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

А у дикарей даже секса-то еще нет - до проблем геев там еще очень далеко.

anonymous
()
Ответ на: комментарий от hfucker

Это навязывается.

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

anonymous
()
Ответ на: комментарий от anonymous

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

hfucker
()
Ответ на: комментарий от hfucker

LOL, все с точностью до наооборот.

В каком месте? Контрактная армия, человеческие условиях в тюрьмах, отделение религии от государства - это все нормальные условия. А теперь посмотри, что у дикарей творится - с точностью до наоборот, деградация.

anonymous
()
Ответ на: комментарий от hfucker

Я говорю про навязывание толерантного отношения к данному явлению.

Они просто инвалиды, им так же нужны права.

anonymous
()
Ответ на: комментарий от anonymous

отделение религии от государства

Кстати, в Израиле, ЕМНИП, нет этого отделения, к примеру. А в России, внезапно, есть.

hfucker
()
Ответ на: комментарий от anonymous

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

</thread>

hfucker
()
Ответ на: комментарий от hfucker

Кстати, в Израиле, ЕМНИП, нет этого отделения, к примеру.

Ну это чушь. Зато факт в том, что там террористы в тюрьмах живут лучше, чем среднестатистический россиянин.

А в России, внезапно, есть.

Россия это вообще феодальное государство.

anonymous
()
Ответ на: комментарий от anonymous

Россия это вообще феодальное государство.

Одно радует: во всем мире 95% идиотов, а в России только 89,9%.

anonymous
()
Ответ на: комментарий от hfucker

«Никогда не трепи языком о том, о чем представления не имеешь. Это чревато.»

Анонiмус. Известный философ, математик и эксперт про правам ЛГБТ.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.