P=NP тред #1 Обсуждаем пикрил! Лично мне кажется, что они равны. Если бы существовала задача, лежащ
Аноним
22/06/23 Чтв 14:46:01
№
1
Обсуждаем пикрил!
Лично мне кажется, что они равны. Если бы существовала задача, лежащая в NP, но не лежащая в P, какой-нибудь из миллионов индусов-прогеров, ее бы уже нашел.
Интересный для темы факт: существует доказательство невозможности сортировки массива длины n быстрее, чем за O(n*log(n)). Ну, это для тех, чья жопа чувствует, что правильный ответ "не равно" -- можете попытаться построить задачу-контрпример, усложнив обычную сортировку.
Кидайте сюда литературу по теме.
Хуй знает. Я как дата сайентист после выпуска из университета (изучал там теорию вычислимости) пришел к мысли, что проблема P=NP максимально завязана на проблеме человеческого разума, то есть необходимости построения математической теории человеческого разума, которая бы четко объяснила смысл появления разума или их зачатков у млекопитающих, поиска общих правил-уравнений, по которым происходит обучение в мозгу, а также зачем млекопитающим нужен сон и что из себя представляют ночные сны. И возможно такая теория должна быть геометрической, очень охуеной и простой, с топологическими пространствами, с новыми метриками и новыми понятием расстояния.
Истинность P=NP означала бы, что увидеть что-то также просто, как и сделать это. Что, в общем, правда: допустим, "каждый, кто знает о смерти, умрет". Хотя, многие люди считают, что это не так, и сделать что-то сложнее, чем увидеть. Это потому что их сознание не предназначено для "увидеть". За них это делает внешний мир. Еще, истинное P=NP свело бы весь мир к тульповодству -- представил что-то, и оно сразу есть.
Можно было бы использовать все это для создания пост-человека с его разумом. Это была бы победа над демиургом.
Для доказательства истинности P=NP достаточно найти полиномиальное решение одной NP-полной задачи...
мимоОП
> Если бы существовала задача, лежащая в NP, но не лежащая в P, какой-нибудь из миллионов индусов-прогеров, ее бы уже нашел.
Проблема не в том, чтобы найти такую задачу, а в том, чтобы доказать, что она действительно обладает указанными тобой свойствами. Так что программисты тут ни при чём. Программистам как раз уже давно известно огромное количество задач, лежащих в NP, про которые при этом не удаётся доказать (или опровергнуть), что они не лежат в P.
> существует доказательство невозможности сортировки массива длины n быстрее, чем за O(n*log(n)).
Во-первых, быстрее чем за Omega(n log(n)). Во-вторых, такого утверждения, как ты озвучил, вообще нет. Оно верно только для отдельно взятой модели вычисление - модели, в которой из разрешённых операций есть только сравнения.
> Кидайте сюда литературу по теме
Начни со школьных учебников по информатике. У тебя явно где-то на том уровне уже пробелы есть.
> изучал там теорию вычислимости
Точно изучал? Дело, видишь ли, в том, что теория вычислимости имеет примерно никакое отношение к классам сложности вроде P и NP. А теория, в которой эти классы изучаются, называется теорией сложности вычислений.
зы. Теория вычислимости тоже существует. Но она про другое.