Действие какого романа происходит во вселенных, где P=NP?

Интересно, писал ли кто-нибудь роман, действие которого происходит во вселенной, где P=NP, если их больше одной, какая из них была первой?

введите описание изображения здесь

В этой вселенной все проблемы, которые могут быть проверены за полиномиальное время (NP) (при наличии решения), также могут быть решены за полиномиальное время (P).

по уважительной причине, я думаю. Я вижу диалог прямо сейчас.
Грег Иган написал Dark integers и Luminous, которые посвящены вычислимости и сложности в чистых алгебраических настройках. Если это сработает, сработает и роман о P=NP :)
Домашняя страница MathFiction могла бы стать хорошей отправной точкой для чего-то подобного.
Не роман, но Рассел Импальяццо (ведущий исследователь теории сложности) написал короткую статью, описывающую пять миров, в которых происходят такие вещи (вселенная Algorithmica имеет P = NP, Cryptomania гарантирует криптографию с открытым ключом и т. д.). Просто подумал, что я упомяну, если вам интересно более теоретическое представление о том, как будет выглядеть мир с P = NP. blog.computationalcomplexity.org/2004/06/…
Доктор G +1, но я не уверен, какие версии рассказов Игана вы читали :P, но я принял это за то, что значения истинности арифметических утверждений ведут себя как вращение квантовой частицы, а вычисление математических результатом было переворачивание этих значений истины в ущерб «другой, параллельной вселенной». На саму физику повлияло изменение правил математики, поэтому повсюду царил хаос, когда «другие» сопротивлялись. (И да, у меня есть докторская степень по чистой математике)
...и откуда вы знаете, что P=NP не соответствует нашей вселенной? Дайте мне знать, и я поделюсь с вами миллионом долларов.
@DavidRoberts Я должен был сформулировать вопрос как роман, действие которого происходит во вселенной, где мы знаем, что P = NP :) Re: Иган, я интерпретировал эту историю как поворот интенсионального определения. Наша теория основана на интенсиональном определении, это не означает, что вселенная согласна, и, поскольку мы не пытались проверить экстенсиональную версию наших определений, физическая вселенная может не согласиться.
Может быть, все они... Так как это нерешенная проблема на данный момент. :-)
Можете ли вы объяснить в очень простых терминах, что означает P=NP и как мы узнаем, находится ли книга, которую мы читаем, в этой вселенной?
@Wikis: Во вселенной P = NP найти правильное решение большой и четко определенной иерархии проблем было бы так же сложно, как признать , что предлагаемое решение такой проблемы является правильным. Например, в нашей вселенной признать, что произведение искусства является великим, кажется намного проще, чем создать великое произведение. Во вселенной, где P=NP, требуемое количество усилий будет таким же или лишь немного больше, если смотреть на него с точки зрения масштаба решаемой проблемы. Легкий взлом почти всех форм шифрования — еще один признак вселенной P=NP.
@DrG: Грег Иган, вероятно, мог бы написать роман, в котором P и NP являются главными героями. Этот парень делает Ким Стэнли Робинсон похожим на Джорджа Лукаса.

Ответы (10)

Звездный путь, разное, 1966 (самое раннее появление)

P=NP во вселенной Star Trek, но люди там об этом не знают. Доказательство:

  1. Шифрование есть, но его всегда можно сломать. P=NP позволит взломать все, кроме одноразовых блокнотов, но Федерация упорно продолжает использовать шифры на основе NP.

  2. Эффективность универсального переводчика. P=NP упростит изучение новых языков, по крайней мере, для компьютера. Системы обучения были бы настолько простыми и понятными в реализации, что ни один лингвист не остался бы без работы.

  3. Эффективность биофильтра. Транспортер регулярно фильтрует неизвестные организмы, вирусы и другие опасности, когда члены экипажа доставляются на борт корабля. Но термин «биофильтр» вводит в заблуждение, поскольку он напоминает некое сито, которое улавливает все плохое и пропускает только хорошее. В действительности запуск такого «фильтра» по транспортным данным был бы матерью всех проблем индуцированного изоморфизма подграфов , поскольку вам пришлось бы идентифицировать все структуры размером с вирус в организме, битком набитом такими структурами. P=NP волшебным образом убирает экспоненту, связанную с входными данными, что делает такие проблемы неразрешимыми даже для небольших графов.

  4. Самосознательный машинный интеллект создается с легкостью. Уэсли Крашер создал его случайно. Как и Ричард Дейстром. Компьютер «Энтерпрайз Д» приготовил «Мориарти» в запасных циклах, доктор Фараллон создал «Экзокомпы» и так далее. Все, что вам, кажется, нужно сделать, это построить что-то, эквивалентное системе доказательства теорем, и позволить ей работать достаточно долго, чтобы наткнуться на доказательство того, что P или какой-либо другой податливый класс эквивалентен NP, и система отправится в гонку.

Или, возможно, обитатели «Звездного пути» разрушают полиномиальную иерархию технологическими средствами. Федерация, Борг и т. д., кажется, имеют свободный доступ к машинам времени, червоточинам, экзотической материи и сверхсветовым сигналам, поэтому они могут использовать замкнутые времяподобные кривые для вычислений. Это , по словам Скотта Ааронсона , позволило бы им эффективно решать проблемы, связанные с PSPACE.

+1 за использование доказательств из мира, чтобы показать что-то. Самый превосходный.
Я думаю, что они просто решают три вопроса, о которых вы говорите, с помощью чистой вычислительной мощности. DTM может решить те же проблемы, что и NTM, но занимает больше времени. Итак, если их инженерные навыки достаточно сумасшедшие, они могут выкашливать действительно быстрые (параллельные) компьютеры (также они, вероятно, нашли пару хороших эвристик для некоторых NP-сложных задач по пути). Так что я не уверен, как применимы ваши аргументы.
@Blue Возможно, мне следовало написать, что P=NP позволяет взламывать все полезные , кроме одноразовых блокнотов. Если вы не можете проверить расшифровку за полиномиальное время, что означает наличие криптосистемы вне NP, то даже с помощью ключа расшифровка невозможна с вычислительной точки зрения. Это для меня не полезная криптосистема.
@bitmask: где-то в технических руководствах говорится, что «Звездный путь» запускает ядро ​​​​компьютера внутри модифицированного поля деформации, где время течет с другой скоростью.
@MichaelEdenfield: Если существуют методы решения проблем, строго более мощные, чем очень быстрая DTM, и для практических приложений P и NP утратили актуальность, это само по себе является очень убедительным доказательством того, что P = NP во вселенной. Во вселенной P!=NP открытие таких методов маловероятно.
@Tynam P и NP определены строго с точки зрения того, что можно делать с детерминированными и недетерминированными машинами Тернига; просто нет смысла говорить о них вне этого контекста. Уже есть доказательства того, что квантовые компьютеры могут обеспечить способ выполнения недетерминированных вычислений, например...
@MichaelEdenfield: Хороший вопрос; Я не думал об аспектах квантового компьютера и NDTM. Тем не менее практическая разница между вселенной P=NP и вселенной значительно более мощных ND-вычислений, вероятно, невелика. (Но тогда я не уверен, что человеческий мозг значительно мощнее, чем DTM; параллелизм — это не то же самое, что алгоритмическая сложность.)
Не могли бы вы указать дату этого?
@AncientSwordRage Дата чего?
@ Кайл, дата, когда, как вы думаете, сериал «Звездный путь» впервые был изображен как P = NP.
@AncientSwordRage Выбирая из моих примеров, я думаю, что это должен быть первый эпизод с использованием универсального переводчика в ситуации первого контакта. В TOS это будет 10-й эпизод первого сезона «Корбомитовый маневр», когда « Энтерпрайз » столкнулся с Баалоком и забавным мячом Первой Федерации.
@kyle, значит, это 1966 год, который является претендентом. Не могли бы вы возражать против того, чтобы я отредактировал это в вашем ответе?
@AncientSwordRage нет, давай.

Антитела, Чарльз Стросс, 2 000

Короткий рассказ, основанный на том факте, что решение P=NP является необходимой предпосылкой для развития компьютерного интеллекта. Это доступно в его книге Toast . Стросс разместил полный текст этой книги в Интернете. ( Эта ссылка приведет вас прямо к истории.)

И, согласно сайту Стросса, история была такой:

Опубликовано в Interzone # 157; переиздан в «Лучшей научной фантастике года № 18» (под редакцией Гарднера Дозуа). Упоминается в «Списке рекомендуемой литературы» Locus за 2000 год. Вошел в шорт-лист премии Теодора Стерджена 2001 года (проиграл «Истории Тендолео» Яна Макдональда).

Другая книга Стросса, посвященная этому, — «Архивы злодеяний », где Алан Тьюринг решил P=NP, но затем они обнаружили, что это открывает доступ к Хтоническим мирам, так что теперь существует целая ветвь правительства, чтобы не допустить, чтобы это открытие стало достоянием общественности. .

В серии Вернора Винджеса «Зоны мысли» («Болтовня», «Огонь в глубине », «Глубина в небе » и готовящиеся к выходу «Дети неба ») вычисления в некоторых частях галактики проще, что позволяет выполнять такие вещи, как искусственный интеллект и сверхсветовые путешествия.

Было высказано предположение (но прямых доказательств в книгах нет), что P=NPв этих зонах.

Есть косвенные доказательства? Насколько я помню, вычисления за пределами медленной зоны отличаются (тезис Черча верен только в медленной зоне), и что-то вроде P = NP не обязательно должно применяться или даже иметь смысл там.
В « Пожаре в глубине» наездники Скоде находят веру Фама в шифрование с открытым ключом забавной. Отсюда можно сделать вывод, что P == NPв Запределье.
Не обязательно — квантовые компьютеры теоретически могли бы решать NP-полные задачи за полиномиальное время, даже без P=NP.
Нет, они не могут. Операции, на сложность которых полагаются наиболее распространенные алгоритмы шифрования с открытым ключом — факторинг, дискретный журнал — не являются (считается) NP-полными. Это проблемы, которые квантовые компьютеры теоретически могут решить за полиномиальное время. При этом существуют алгоритмы шифрования с открытым ключом, основанные на NP-полных проблемах, но они не получили широкого распространения (пока...)
@BlueRaja В настоящее время мы не знаем, как использовать квантовый компьютер для эффективного решения полных NP-задач, но вы утверждаете, что P < NP <= BQPэто неверно, и я не знаю доказательств этого. Я согласен, что это, вероятно, ложь, но вы утверждаете это как факт.
@Code: Да, извините, я говорил невнимательно. Я имел в виду, что это не известно (или не считается) теоретически возможным.
Я собирался сказать «Зоны мысли». Я не уверен, что то, что P = NP, является буквально верным, поскольку возможно, что в любом конкретном месте в зоне наша интуиция о том, что вы можете построить NP-задачу, которую не можете легко решить, остается верной. Но я думаю, что это достаточно похоже, чтобы его стоило упомянуть, поскольку вы можете переместиться (или отправить сообщение) в более высокую зону, где ваша проблема будет легко решаема.

В фанфике Элиезера С. Юдковски « Гарри Поттер и методы рационального мышления » Гарри получает машину времени и пытается разложить на множители произведение двух больших простых чисел , используя эту машину, с несколько странным результатом. Так что это не совсем дано NP=P, но кажется вероятным.

Это не имеет смысла. Задача принадлежит P, если существует некоторая машина Тьюринга, решающая эту задачу (определение NP аналогично). Неважно, существуют ли другие мыслимые средства решения этой проблемы. Взломав временные петли, Гарри вышел за рамки вопроса P=NP.
Да, если бы его тест прошел успешно, это означало бы, что существует «более сильное» вычислительное устройство, чем машина Тьюринга, и поэтому он опроверг тезис Черча. Поэтому, если вы оставите NP определенным с помощью машин Тьюринга, это не докажет, что «NP = P».
IIRC было доказано, что P = PSPACE (что сильнее, чем P = NP) для машины Тьюринга, оснащенной возможностью отправлять данные назад во времени, даже если она подчиняется самосогласованности Новикова. Все еще возможно, что P = PSPACE для обычных машин Тьюринга, но это считается еще менее правдоподобным, чем P = NP, теоретиками «основного направления» сложности.

«Ревущая труба » Спага де Кампа и Флетчера Пратта, опубликованная в мае 1940 года в журнале Unknown. Здесь психологи утверждают, что шизофреники на самом деле мысленно получают доступ к альтернативным вселенным, и, применяя правильные уравнения, можно отправиться в эту альтернативную вселенную и вернуть разум человека обратно в нашу вселенную. Это было интеллектуальное упражнение, которое главный герой Гарольд Ши решает проверить. Он в шутку говорит о путешествии с помощью syllogismobile, но оно включает в себя изучение и построение логики назначения во вселенной и проговаривание ее вслух. Обычно это начинается с «если P равно не P...» и продолжается оттуда. Во всей серии Enchanter они прыгают по вселенной через мифологию, сказку и классические произведения, делая это.

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

Однако «NP» в «P = NP» не означает «не P». Эта формулировка могла быть основана на недоразумении, но я уверен, что проблема P и NP не была сформулирована к 1940 году, поэтому они, вероятно, просто хотели установить противоречие («P» является общим предложением; предполагая, что P, а не P , за этим может последовать все что угодно.) Насколько мне известно, вопрос P vs NP был впервые задан как таковой в 1971 году.

Немезида, Айзек Азимов, 1989 г.

Он говорит о невозможности и последствиях вселенной, где законы физики неприменимы.

Пожалуйста, укажите дату вашего ответа в следующий раз и объясните, почему это явно относится к P = NP.

Эффект практики , Дэвид Брин, 1984 г.

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

Пожалуйста , отредактируйте , почему вы думаете, что это так.

В рассказе Маргарет Вайс и Трейси Хикман «Стражи Звездного щита » были компьютеры/искусственный интеллект, которые могли мгновенно ответить на любой вопрос , отправив вопрос самому себе во времени, дав ему «время» для его решения. Единственная загвоздка в этом заключалась в том, что компьютер должен был быть «бодрствующим» достаточно долго, чтобы решить эту проблему (что-то вроде «Глубокой мысли» из «Автостопом по Галактике», требующей 10 миллионов лет, чтобы решить вопрос о жизни, Вселенной и обо всем остальном).

Хотя я не знаю, относится ли это точно ко всему P = NP, оно решает предложение переменной/решения в вопросе.

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

Если я не ошибаюсь, в « Оборванных астронавтах » Боба Шоу один из персонажей тратит немного времени, объясняя другому, почему число пи равно 3. Если пи равно 3, я могу только представить, на что похожа остальная физика. (Я вообще помню эту сцену только потому, что вся сцена была немного неуместной, что было довольно необычно для книги — в остальном это был хороший рассказ).

Как это связано с p=np?
Действие какого романа происходит во вселенных, где P=NP?
СпросиСетьПолитика конфиденциальности1y, 2v