М.Двач / Математика

117 Кб, 960x720
P=NP тред #1 Обсуждаем пикрил! Лично мне кажется, что они равны. Если бы существовала задача, лежащ 22 июня 2023, 14:46 103234 В конец треда | Веб

P=NP тред #1
Обсуждаем пикрил!

Лично мне кажется, что они равны. Если бы существовала задача, лежащая в NP, но не лежащая в P, какой-нибудь из миллионов индусов-прогеров, ее бы уже нашел.

Интересный для темы факт: существует доказательство невозможности сортировки массива длины n быстрее, чем за O(n*log(n)). Ну, это для тех, чья жопа чувствует, что правильный ответ "не равно" -- можете попытаться построить задачу-контрпример, усложнив обычную сортировку.

Кидайте сюда литературу по теме.

Ответы238377378

2 22 июня 2023, 20:16 2 103238

>>103234 (OP)
Хуй знает. Я как дата сайентист после выпуска из университета (изучал там теорию вычислимости) пришел к мысли, что проблема P=NP максимально завязана на проблеме человеческого разума, то есть необходимости построения математической теории человеческого разума, которая бы четко объяснила смысл появления разума или их зачатков у млекопитающих, поиска общих правил-уравнений, по которым происходит обучение в мозгу, а также зачем млекопитающим нужен сон и что из себя представляют ночные сны. И возможно такая теория должна быть геометрической, очень охуеной и простой, с топологическими пространствами, с новыми метриками и новыми понятием расстояния.

Ответы239412

3 22 июня 2023, 23:01 3 103239

>>103238
Истинность P=NP означала бы, что увидеть что-то также просто, как и сделать это. Что, в общем, правда: допустим, "каждый, кто знает о смерти, умрет". Хотя, многие люди считают, что это не так, и сделать что-то сложнее, чем увидеть. Это потому что их сознание не предназначено для "увидеть". За них это делает внешний мир. Еще, истинное P=NP свело бы весь мир к тульповодству -- представил что-то, и оно сразу есть.

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

Для доказательства истинности P=NP достаточно найти полиномиальное решение одной NP-полной задачи...
мимоОП

4 30 июня 2023, 18:19 4 103377

>>103234 (OP)
> Если бы существовала задача, лежащая в NP, но не лежащая в P, какой-нибудь из миллионов индусов-прогеров, ее бы уже нашел.
Проблема не в том, чтобы найти такую задачу, а в том, чтобы доказать, что она действительно обладает указанными тобой свойствами. Так что программисты тут ни при чём. Программистам как раз уже давно известно огромное количество задач, лежащих в NP, про которые при этом не удаётся доказать (или опровергнуть), что они не лежат в P.

5 30 июня 2023, 18:22 5 103378

>>103234 (OP)
> существует доказательство невозможности сортировки массива длины n быстрее, чем за O(n*log(n)).
Во-первых, быстрее чем за Omega(n log(n)). Во-вторых, такого утверждения, как ты озвучил, вообще нет. Оно верно только для отдельно взятой модели вычисление - модели, в которой из разрешённых операций есть только сравнения.

> Кидайте сюда литературу по теме
Начни со школьных учебников по информатике. У тебя явно где-то на том уровне уже пробелы есть.

6 1 июля 2023, 02:48 6 103412

>>103238
> изучал там теорию вычислимости
Точно изучал? Дело, видишь ли, в том, что теория вычислимости имеет примерно никакое отношение к классам сложности вроде P и NP. А теория, в которой эти классы изучаются, называется теорией сложности вычислений.

зы. Теория вычислимости тоже существует. Но она про другое.

Обновить тред
« /math/В начало тредаВеб-версияНастройки/a//b//mu//s//vg/Все доски

Скачать тред только с превьюс превью и прикрепленными файлами

Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах.Подробнее

Пользуетесь скринридером — пишите, что можно улучшить.
Host-Food.ru — надёжный хостинг от 12 руб/мес | Free DNS
Зеркала М.Двача: m2ch.hk, m2ch.lib, m2chfapiswfw2wcakptqp4o6ltgchvjuxfab7urxlduraomtlnhw5xad.onion