LINUX.ORG.RU

Вопрос по P = NP

 ,


0

2

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

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

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

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

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

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

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



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

Почему эта ебанутая шизофреническая проблядь еще не забанена?

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

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

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

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

Главное не разрешать им искусственное оплодотворение (для лесбиянок) и суррогатное материнство (для геев), которое позволит передать их признаки дальше.

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

ибо неизвестно как это повлияет на психику ребёнка (геем он не станет от этого, впрочем, но травму получить может).

А как же исследования (уже существующие)? Или бытовая логика надежнее?

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

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

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

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

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

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

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

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

Вообще то, считается, что википедия лоббирует LGBT. Имея это в виду, весьма странный пруф. Собственно, тут и без психологов очевидно, что все это ведет к серьезной деформации детской психики. Особенно учитывая то, что люди, независимо от их этих самых предпочтений, не идеальны, а порой, внезапно, непорядочны. Ребенок рискует стать очевидцем весьма недетских сцен.

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

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

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

Кроме прямых вбросов и флеймообразующих тем, вообще невозможно достоверно сказать, что делает анонiмус, чем занимается. Ясно, что в том числе, засиранием ЛОРчика, выдумыванием и навязыванием несуществующих проблем, в интересах своей шизофрении, тупняком, и так далее.

починил, не благодари.

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

весьма странный пруф

Википедия тут просто как референс.

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

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

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

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

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

чтобы он был счастлив

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

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

Внутренний голос все равно будет все время подсказывать

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

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

Доказать вообще ничего невозможно. Логика — это фикция, порожденная человеческим умом, которая стала религией в наше время.

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

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

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

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

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

Во что мне поверить, чтобы принять такой аргумент? Ведь у меня нет ни списка всех научных открытий, ни статистики по ним, я не могу проверить его.

anonymous
()

Interesnaya tema

Interesnaya tema. Stranno, chto avtora zabanili (vozmozhno, ego zabanili za druguyu temu).

Mne kazhetsya, oshibka avtora v sleduyushchem:

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

NDMT kak raz imho vyigrysh dast (ya pravda ne spetsialist). NDMT — eto kak DMT, tolko ono na kazhdom shage mozhet forkat'sya. T.ye. eski na K-tom shage u nas est odna NDMT, to na (K+1)-vom shage u nas mozhet byt' uzhe neskolko NDMT (kazhdaya iz kotoryh bydet rabotat so svoim podmnozhestvom variantov), a na (K+2)-om shage — voobshche dohrena NDMT.

T.ye., ochen uslovno govorya, dlya togo chtoby reshyt' dannuyu zadachu, NDMT dostatochno vsyego 2 shaga: pered pervym shagom ona forkaetsya po kolichestvu saytov (kazhdaya mashina skachivaet 1 sayt), a pered vtorym shagom kazhdaya mashina forkaetsya po kolichestvu ssylok na sayte (kazhdaya mashina proveryayet 1 ssylku). Na samom dele konechno ne tak, na samom dele chtoby vychitat' spisok saytov nuzhno hotya by M shagov (M — kol-vo saytov v spiske), a chtoby vychitat' vsye ssylki na sayte nuzhno hotya by N shagov (N — maksimalnoye kol-vo ssylok na sayte), itogo O(M+N). No eto luchshe, chem DMT, kotoroy pri takom algoritme nuzhno O(M*N) shagov.

P.S.: I eshcho. Esli v kakoy-to zadache NDMT ne dayot preimushchestva pered DMT, eto yeshcho ne znachit chto P=NP (takih zadach dohrena, naprimmer, prosummirovat' vsye chisla v spiske). Chtoby govorit' P=NP, nuzhno chtoby vo vsyeh zadachah NDMT ne davala preimushchestva. (Na samom dele ne tak.)

sasha1024
()
Ответ на: Interesnaya tema от sasha1024

Модераторы! Прошу оградить мою нежную душевную организацию от этого транслитного скама! Это ЛОР или где?

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