Это уже давно ломает мне мозг. Насколько нам сейчас говорит физика, мы живем в мире, где физические законы индуктивны, но не детерминированы, потому что на каком-то базовом уровне существует то, что мы считаем истинной случайностью.
Итак, давайте представим мир, в котором все совершенно детерминировано, в нем нет лежащей в основе случайности. Следовательно, каждый физический процесс может быть решен детерминированным алгоритмом точно каждый раз. В таком мире P = NP? Если мы можем представить себе такой мир, значит ли это, что P = NP? Или две концепции детерминизма в информатике и физике никак не связаны? Должна быть хоть какая-то связь. Пожалуйста, не отвечайте одним словом, я хочу получить некоторое представление здесь.
Абстрактная математика не обязательно должна быть связана с физикой. Есть много вещей, которые математики обычно рассматривают (например, неизмеримые множества и т. д.), которые не могут существовать в физическом мире.
В частности, законы физического мира не имеют отношения к проблеме P=NP.
Детерминированная вселенная может не быть квантовой вселенной, и в этом случае алгоритмы, подобные алгоритму Шора, будут невозможны; будет ли квантовый или постквантовый метод решения NP задач в P-времени неизвестно. Предположим, что есть. Это не будет означать, что P = NP; Алгоритм Шора относится к классу сложности BQP : квантовое полиномиальное время с ограниченной ошибкой.
Класс сложности NP — это другой вид недетерминированности, чем наши текущие знания о квантовой механике и ее недетерминированном характере. Мы знаем это, потому что ни один известный квантовый компьютер не может решать NP-полные задачи за полиномиальное время. Это связано с тем, что для решения NP-полных задач за P-время вам потребуется создать n-1 новых экземпляров программы в каждой точке решения с n возможными решениями. Это не совсем «пробовать все одновременно», но близко к этому. Ни один известный квантовый компьютер не может «попробовать все сразу»; это потому, что квантовые схемы недостаточно мощны.
Предположим, что мы нашли новый тип квантового компьютера, который может решать NP-полные задачи за P-время. Должна ли Вселенная быть такой или нет , вероятно, будет вопросом для философов. Но, конечно же, вы можете видеть, что в детерминированной вселенной этот квантовый компьютер [вероятно] был бы недоступен. Поэтому, если вы создадите цифровой мир, населенный разумными существами, и сделаете этот мир детерминированным, эти существа, вероятно, не смогут вычислить столько же, сколько вы, за любой заданный период времени.
При всем при этом может оказаться, что классические компьютеры можно использовать для решения NP-задач за P-время, если окажется, что P = NP. В этом случае совершенно не имеет значения, является ли мир детерминированным или индетерминированным. На данный момент мы просто не знаем. Если вы хотите, чтобы ваш мозг был взорван в отношении вычислений и физики, посмотрите этот учебник по вычислениям черных дыр , а затем перейдите к обсуждению Скоттом Ааронсоном недавних споров о брандмауэрах . «Что можно реально вычислить в нашей вселенной?» увлекательный вопрос. Возможно, существует глубокая связь между вычислениями и физикой!
Вопрос о том, имеет ли P = NP не отношение к детерминированности процессов, не имеет отношения к тому, сколько усилий может потребоваться детерминированным по сравнению с недетерминированными пошаговыми процессами для достижения решений конкретных типов проблем. Рассматриваемый недетерминизм всегда ограничен конечным, перечислимым выбором альтернатив, поэтому для любого из рассматриваемых недетерминированных процессов всегда существует детерминистический «эквивалент» (например, полученный в результате исчерпывающего перебора всех альтернатив некоторым систематическим способом).
Проще говоря, Майкл говорит, что вопросы математики (такие как P=NP) не относятся к свойствам какого-либо физического мира. Физики используют и развивают математику, математика не принимает физические наблюдения или идеи в качестве входных данных.
Митч
лабройер
Майкл
лабройер
Майкл
лабройер