Кажется, что многие люди считают, что , отчасти потому, что они считают, что факторинг не является разрешимым с помощью политикана. (Шива Кинтали перечислил несколько других проблем кандидата здесь ).
С другой стороны, Grötschel, Lovász и Schrijver написали, что «многие люди считают, что ». Эту цитату можно найти в « Геометрических алгоритмах и комбинаторной оптимизации», и Шрайвер делает аналогичные утверждения в « Комбинаторной оптимизации: многогранники и эффективность» . Эта картина проясняет, где Джек Эдмондс стоит по этому вопросу.
Какие доказательства подтверждают веру в ? Или поддержать ?
cc.complexity-theory
np
conditional-results
Остин Бьюкенен
источник
источник
Ответы:
Теорема 3.1 об односторонних перестановках и языках-свидетелях К. Хоман и М. Тхакур, Журнал компьютерных и системных наук, 67 (3): 608-622, ноябрь 2003 г. [ as .pdf ] утверждает, что тогда и только тогда, когда существуют (в худшем случае) односторонние перестановки. Теорема 3.2 напоминает еще 10 гипотез, которые, как было показано, эквивалентны .P≠UP∩coUP P≠UP∩coUP
Также у нас есть веские основания предполагать, что . Таким образом, приведенная выше теорема и гипотеза веские основания полагать, что .UP≠NP P≠NP∩coNP
Отказ от ответственности: я переместил редактирование моего ответа Мохаммедом Аль-Туркистани на этот вики-ответ сообщества. Он считает, что он прекрасно отвечает на вопрос, поскольку широко распространено существование односторонних перестановок. Я сам еще недостаточно понимал разницу между односторонними функциями «наихудшего» и «среднего» случая, чтобы утверждать, что это действительно отвечает на вопрос.
источник
Я считаю, что существуют очень качественные генераторы случайных чисел с очень эффективным использованием пространства. Несмотря на это убеждение, я обычно использую твистер Mersenne в своем коде, который является высококачественным, но не очень экономным. Отсутствует связь между космической эффективностью и NP∩coNP, просто ощущение, что есть связь.
Позвольте мне привести одну причину, по которой я считаю, что «истинная случайность» может быть эффективно смоделирована / аппроксимирована очень пространственно. Мы знаем, что можно создавать псевдослучайные числа, которые являются достаточно случайными для всех практических целей (включая криптографию). Мы также знаем, что использование (небольшого количества фиксированных) больших простых чисел при построении генераторов псевдослучайных чисел редко является плохой идеей. Мы знаем из предположений, подобных предположениям Римана, что почти все простые числа содержат высокую степень случайности, но мы также знаем, что мы еще не можем строго доказать это.
Есть ли интуитивное объяснение, почему простые числа ведут себя как случайные числа? Простые числа являются дополнением к составным числам. Дополнение к набору с хорошим поведением зачастую сложнее, чем к исходному набору. Составные числа состоят из простых чисел, что, в свою очередь, уже придает этому набору определенную сложность.
Фон Я однажды попытался понять, почему P ≠ NP сложно. Я задавался вопросом, может ли аппроксимация групп внутренней симметрии экземпляра проблемы нильпотентными группами не привести к «алгоритму абстракции», способному понять внутреннюю структуру экземпляра проблемы. Но потом я понял, что даже вычисление структуры нильпотентной группы содержит факторинг как частный случай. Вопрос о простых подгруппах циклической группы порядка n эквивалентен определению простых множителей n. И классификация конечных нильпотентных группсодержит еще худшие подзадачи, связанные с изоморфизмом графов. Этого было достаточно, чтобы убедить меня, что такой подход не поможет. Но моим следующим шагом была попытка понять, почему факторинг затруднен, и ответ на этот вопрос - то, что я придумал. Этого было достаточно, чтобы убедить меня, поэтому, возможно, это будет убедительно и для других людей. (Я тогда не знал о группоидах или обратных полугруппах, которые, вероятно, более пригодны, чем нильпотентные группы для обработки внутренних симметрий. Тем не менее, аргумент, почему такой подход не будет эффективным, остается неизменным.)
источник