Причины верить (или нет)

27

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

С другой стороны, Grötschel, Lovász и Schrijver написали, что «многие люди считают, что ». Эту цитату можно найти в « Геометрических алгоритмах и комбинаторной оптимизации», и Шрайвер делает аналогичные утверждения в « Комбинаторной оптимизации: многогранники и эффективность» . Эта картина проясняет, где Джек Эдмондс стоит по этому вопросу.P=NPcoNP

Какие доказательства подтверждают веру в ? Или поддержать ?PNPcoNPP=NPcoNP

Остин Бьюкенен
источник
Определите «причину». Там действительно нет доказательств, так или иначе. Это не то, что можно проверить экспериментально. До тех пор, пока у нас не будет доказательств, так или иначе, единственные «причины верить» - это интуитивные чувства, либо какая-то проблема в не является полиномиальной, либо какой-то инстинктивный инстинкт, которым они все являются. NPcoNP
2013 года
2
Я надеялся на такие ответы, как то, что Скотт Ааронсон дал для P против NP .
Остин Бьюкенен
1
многие из тех же самых идей Ааронсона применимы. С чем-то не согласен. Есть много косвенных доказательств, включая экспериментальные данные, некоторые из которых перечислены Ааронсоном.
2013 года
5
Теорема 3.1 об односторонних перестановках и языках-свидетелях К. Хоман и М. Тхакур, Журнал компьютерных и системных наук, 67 (3): 608-622, ноябрь 2003 г. [ as .pdf ] утверждает, что P ≠ UP∩ coUP тогда и только тогда, когда существуют (в худшем случае) односторонние перестановки. Теорема 3.2 напоминает еще 10 гипотез, которые, как было показано, эквивалентны P ≠ UP∩coUP.
Томас Климпел
9
Я думаю, что факторинг ∈ P на много, много порядков более вероятен, чем P = NP ∩ coNP, так что это, конечно, не причина, по которой я считаю P = NP ∩ coNP.
Питер Шор

Ответы:

5

Теорема 3.1 об односторонних перестановках и языках-свидетелях К. Хоман и М. Тхакур, Журнал компьютерных и системных наук, 67 (3): 608-622, ноябрь 2003 г. [ as .pdf ] утверждает, что тогда и только тогда, когда существуют (в худшем случае) односторонние перестановки. Теорема 3.2 напоминает еще 10 гипотез, которые, как было показано, эквивалентны .PUPcoUPPUPcoUP

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


Отказ от ответственности: я переместил редактирование моего ответа Мохаммедом Аль-Туркистани на этот вики-ответ сообщества. Он считает, что он прекрасно отвечает на вопрос, поскольку широко распространено существование односторонних перестановок. Я сам еще недостаточно понимал разницу между односторонними функциями «наихудшего» и «среднего» случая, чтобы утверждать, что это действительно отвечает на вопрос.

оборота Томас Климпел
источник
0

Я считаю, что существуют очень качественные генераторы случайных чисел с очень эффективным использованием пространства. Несмотря на это убеждение, я обычно использую твистер Mersenne в своем коде, который является высококачественным, но не очень экономным. Отсутствует связь между космической эффективностью и NP∩coNP, просто ощущение, что есть связь.


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

Есть ли интуитивное объяснение, почему простые числа ведут себя как случайные числа? Простые числа являются дополнением к составным числам. Дополнение к набору с хорошим поведением зачастую сложнее, чем к исходному набору. Составные числа состоят из простых чисел, что, в свою очередь, уже придает этому набору определенную сложность.


Фон Я однажды попытался понять, почему P ≠ NP сложно. Я задавался вопросом, может ли аппроксимация групп внутренней симметрии экземпляра проблемы нильпотентными группами не привести к «алгоритму абстракции», способному понять внутреннюю структуру экземпляра проблемы. Но потом я понял, что даже вычисление структуры нильпотентной группы содержит факторинг как частный случай. Вопрос о простых подгруппах циклической группы порядка n эквивалентен определению простых множителей n. И классификация конечных нильпотентных группсодержит еще худшие подзадачи, связанные с изоморфизмом графов. Этого было достаточно, чтобы убедить меня, что такой подход не поможет. Но моим следующим шагом была попытка понять, почему факторинг затруднен, и ответ на этот вопрос - то, что я придумал. Этого было достаточно, чтобы убедить меня, поэтому, возможно, это будет убедительно и для других людей. (Я тогда не знал о группоидах или обратных полугруппах, которые, вероятно, более пригодны, чем нильпотентные группы для обработки внутренних симметрий. Тем не менее, аргумент, почему такой подход не будет эффективным, остается неизменным.)

Томас Климпел
источник
2
Я не уверен, как этот ответ относится к вопросу. Не могли бы вы уточнить?
Матиас
@Matthias Ответ является причиной, почему я считаю, что P ≠ NP∩coNP. Таким образом, проблема, вероятно, не в связи с вопросом, а в том, как объяснить причину. Существует форма математического платонизма, которая предполагает, что математические структуры способны моделировать или аппроксимировать почти все, что может существовать в этом мире. Истинная случайность - это часть того, что может существовать, и ответ пытается объяснить, почему существует интуитивное чувство, что эта случайность уже присутствует в достаточно ограниченных пространствах, чтобы вызвать P ≠ NP∩coNP. (Извините, возможно, я
исправлю / уберу
2
Спасибо. Я думаю, мне было интересно, почему существование космических эффективных генераторов случайных чисел подразумевает, что P NP coNP, потому что я не слышал этого раньше.
Матиас
@Matthias, который я написал «... отсутствует связь между космической эффективностью и NP∩coNP, это просто внутреннее чувство ...» в ответе. Я мог бы попытаться уточнить, но я боюсь, что это не будет хорошо принято. На самом деле, я полагаю, вам скорее нужны независимые ссылки, указывающие в этом направлении, а не мои собственные объяснения. В зоопарке сложности я обнаружил, что приведенные результаты односторонней перестановки «наихудший случай» существуют тогда и только тогда, когда P не равно UP ∩ coUP [ HT03 ]. Газета в сети, но я ее еще не читал ...
Томас Климпел