Я решил задачу P=NP

Первонах!

Если машине нужно просто выдать «1», то недетерминированная будет «бросать монетку», а детерминированная просто выдаст «1».

Но алгоритм задаваемый НМТ не обязан содержать команду недетерминированного перехода

Дано: машина просто выдающая «1». Доказать что она НМТ или опровергнуть это. Действуйте.

Зачем? Это не касается темы

Предположим у васи есть телефон с фотокамерой и без нее. Вася позвонил Пете. По какму из телефонов он звонил?

Это то что Вы спрашиваете. Это не отменяет фотокамеру.

Касается. НМТ не сможет сделать это быстрее никак. Иначе она не НМТ. Вот и всё.

Вася не может позвонить по телефону с фотокамерой, иначе это не телефон с фотокамерой. Вот и все.

Вроде в таких задачах как раз вопрос про общее решение.

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

Вася не может позвонить по телефону с фотокамерой, иначе это не телефон с фотокамерой. Вот и все.

Вася может быстрее дозвониться до Пети, если возьмёт телефон с фотокамерой.

Бред. Вот и всё.

Выносите царя. Ногами вперед

не нашел в твоих рассуждениях ни про P, ни про NP

больше похоже на одного из анонiмусов

цАРЬ написал бы, что анонимус - кукаретик, не нюхавший практического кода на сишке.

Я решил задачу P=NP

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

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

Я решил задачу P=NP

На формальном языке?

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

ну тогда анонiмуса, нiгами впiред

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

logicoop1

Готов поставить на это бессмертную душу.

А что это значит? Согласно википедии

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

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

Bogosort лучшая сортировка.

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

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

Это парадокс похлеще камня.

Я, конечно, понимаю что тебе ничего не поможет, но попробую: https://en.m.wikipedia.org/wiki/Powerset_construction

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

Подумай о том, что закат и восход солнца неминуем. Подумал? Где теперьтвоя свобода воли?

Всё случайно. Вероятности разные.

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

Молодец. Теперь оформляй в виде статьи и забирай свой заслуженный миллион.

Видел тред на одной странице.

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

Опять бред.

... с помощью «подкидывания монетки»(то есть недетерминированного перехода) может не вычислять все возможные состояния ...

Фишка в том, что существуют «вероятностные алгоритмы», «квантовые алгоритмы» и много чего еще неиследованного. Они могут перевести твое «подкидывание монетки» в решение задач на детерминированной МТ, работающей с вероятностями твоей «монетки».

А я за тебя радовался в последние годы, когда вспоминал. А оказывается, болезнь всё это время прогрессировала.

Думаю, что «квантовые алгоритмы» являются псевдонаучным сочинительством околожелтых изданий, а что касается вероятностного алгоритма, то я не вижу тут принципиальной разницы с недетерминированной МТ

Для детерминированной машины необходимо вычислить все ветви

Не обязательно. Точно так же как с НМТ может оказаться, что порядок перебора оптимальный.

«квантовые алгоритмы» являются псевдонаучным сочинительством околожелтых изданий

Это потому что на «реальном» кремнии, чисто случайно, удалось воспроизвести «абстрактную» булеву алгебру, а для «абстрактной» квантовой механики еще нет известного тебе ширпотребного «реального» вычислителя?

вероятностного алгоритма, то я не вижу тут принципиальной разницы с недетерминированной МТ

Допустим, есть такой детерминированный вычислитель с интеренсным тактируемым элементом «монетка», который за полиномиальное время решает твою задачу. И в твоей исходной постановке такой вычислитель существует - это тот самая МТ, «подбрасывающая монетку».

вычислитель с монеткой не является детерминированным

является: это кнопка и монетка с двумя состояниями

вычислитель с монеткой не является детерминированным

Эта придуманная тобой «аксиома» - есть твое «доказательство». Попробуй без этой «аксиомы».

по определению

определение в студию

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

И не говори, натуральный беспредел творится.

Просьба к модераторам очистить тред от мусора

Я не буду тебе ничего доказывать, участники этого треда должны обладать минимальным базисом

это тебе премию Тьюринга или Филдса должны дать?

судя по просьбе к модераторам - Дарвина

похоже, что ты путаешь свободу воли и свободу выбора

определение для анализа будет?

Я не буду тебе ничего доказывать, участники этого треда должны обладать минимальным базисом

Это неловкая попытка прикрыть собственную безграмотность, принизив собеседников?