Должны ли мы считать

30

Многие эксперты считают, что гипотеза верна, и используют ее в своих результатах. Меня беспокоит то, что сложность сильно зависит от гипотезы PN P.PNPPNP

Итак, мой вопрос:

Пока гипотеза не доказана, можно / нужно ли рассматривать ее как закон природы, как указано в цитате из Штрассена? Или мы должны рассматривать это как математическую гипотезу, которая может быть когда-нибудь доказана или опровергнута?PNP

Quote:

«Доказательства в пользу гипотез Кука и Валианта настолько подавляющи, а последствия их неудач настолько гротескны, что их статус, возможно, можно сравнить с состоянием физических законов, а не с обычными математическими предположениями».

[ Приветствие Фолькера Штрассена лауреату Неванлиннской премии Лесли Г. Валиану в 1986 году]

Я задаю этот вопрос при чтении поста Физика результатов в TCS? , Возможно, интересно отметить, что вычислительная сложность имеет некоторые сходства с (теоретической) физикой: многие важные результаты сложности были доказаны при допущении , в то время как в теоретической физике результаты доказаны при допущении некоторых физических законовPNP . В этом смысле можно считать чем-то вроде E = m c 2 . Вернуться к физике результатов в TCS? :PNPE=mc2

Может ли (часть) TCS быть отраслью естественных наук?

Разъяснение:

(см. ответ Суреша ниже)

Можно ли сказать, что гипотеза в теории сложности так же фундаментальна, как и физические законы теоретической физики (как сказал Штрассен)?PNP

VB Le
источник
10
Веб-сайт cstheory.stackexchange.com не подходит для дискуссий. Пожалуйста, отметьте «Какие вопросы мне не следует задавать здесь?» В FAQ .
Цуёси Ито
11
Ну, я надеюсь, что у кого-то будет правильный ответ на мой вопрос. Я нахожу точку зрения Штрассена довольно интересной, и, как ни странно, мы не говорили об этом. Я проверю FAQ сейчас ...
vb le
8
Вы спрашиваете мнение людей, а не факты, поэтому, на мой взгляд, этот вопрос явно не подходит. Вы не должны соглашаться, но я надеюсь, что моя позиция по этому поводу ясна.
Цуёси Ито
30
Я думаю, что этот вопрос очень важен и что в этом случае мы можем сделать исключение из-за тенденции избегать дискуссий.
Гил Калай
3
@ Гил Калай: В этом мире нужно обсудить много важных вещей, но cstheory.stackexchange.com не для них. Пожалуйста, обсудите их где-нибудь еще.
Tsuyoshi Ito

Ответы:

57

Заявление Штрассена необходимо поместить в контекст. Это было обращение к аудитории математиков в 1986 году, когда многие математики не имели высокого мнения о теоретической информатике. Полное утверждение

Некоторым из вас может показаться, что обсуждаемые здесь теории опираются на слабые основания. Они не. Доказательства в пользу гипотез Кука и Валианта настолько ошеломительны, а последствия их неудач настолько гротескны, что их статус, возможно, можно сравнить с состоянием физических законов, а не с обычными математическими предположениями.

Я уверен, что Штрассен имел беседы с чистыми математиками, которые говорили что-то вроде

«Вы строите всю теорию сложности на карточном домике. Что если P = NP? Тогда все ваши теоремы будут бессмысленными. Почему бы вам просто не приложить немного усилий и доказать, что P NP, а не продолжайте строить теорию на таких слабых основаниях ".

В 2013 году, когда P NP был проблемой с призом Клея в течение десятка лет, может показаться трудным поверить, что у любого математика действительно были такие взгляды; однако, я могу лично подтвердить, что некоторые сделали.

Штрассен продолжает, говоря, что мы не должны отказываться от поиска доказательства P NP (таким образом, косвенно подразумевая, что это действительно математическая гипотеза):

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

так что, возможно, я бы назвал это «рабочей гипотезой», а не «физическим законом».

Позвольте мне наконец отметить, что математики также используют такие рабочие гипотезы. Существует большое количество математических работ, доказывающих теоремы, утверждения которых гласят: «Если предположить, что гипотеза Римана верна, то ...».

Питер Шор
источник
1
«Почему вы не просто загадал немного усилий и доказать , что P NP ...» - но , вероятно , огромные усилия уже были поставлены FWD с самого начала гипотезы ....
ВЗН
7
@vzn: вот почему математики, которые говорили подобные вещи, были такими раздражающими.
Питер Шор
хорошо, да, согласились, что математики, может быть, несколько несправедливо, не признают P NP является математически значимым или, возможно, даже фундаментальным, вплоть до, возможно, десятилетий спустя, и приз Клея, вероятно, во многом способствовал этому. Интересным примером этого является исследование Гауэрсом [ полевого медалиста ] доказательства нижних границ монотонной схемы Разборова . и, конечно, гипотеза Римана - это еще одна математическая проблема Клея ... наряду с другими, в основном, математическими ...=?
vzn
20

Я вижу три взаимосвязанных способа понять вопрос:

1) Можем ли мы считать фундаментальным принципом теории сложности вычислений еще до того, как мы сможем это доказать?NPP

2) Распространяется ли принцип за пределы своего узкого математического значения?NPP

3) Можно ли рассматривать принцип как физический закон?NPP

Я думаю, что есть веские причины для ответа «да» или «квалифицировано да» на все эти три вопроса.

Гил Калай
источник
12

Я не уверен, что понимаю. Физический закон (того типа, который вы указываете) - это математическое выражение модели (в этом примере, относительности), которая претендует на захват реальности. Физический закон может быть доказан неверным, если базовая математика неверна, но он также может быть неправильным, если базовая модель изменяется (например, ньютоновская механика). P против NP - это конкретная математическая гипотеза, которая является истинной или ложной (и может быть доказуемо или нет)

Суреш Венкат
источник
Я знаю, что переигрываю с цитатой Штрассена. Меня беспокоит то, что сложность сильно зависит от вопроса P против NP, как физика от его законов (как вы уже выяснили). Таким образом, вопрос: пока гипотеза P против NP не доказана, можно / нужно ли рассматривать ее как физический закон, как указано Штрассен?
vb le
7

Чтобы ответить на ваш оригинальный вопрос:

PNP

«Допущение твердости NP ?: Нет физических средств для решения полных задач NP за полиномиальное время».

Он выступил с хорошей речью в Университете Ватерлоо под названием « Вычислительная неразрешимость как закон физики».

Мухаммед Аль-Туркистани
источник
13
7
+1. После одного из разговоров, которые у меня были с другом, я понял, что вселенная не будет иметь никаких оснований для существования, если P = NP.
labotsirc
2
@labotsirc не могли бы вы привести свои причины?
T ....
5

NLPSPACENPcoNPPNP

Т ....
источник
С математической точки зрения ваш ответ имеет смысл, но вопрос не математический. Я думаю, что P против NP - более естественный и интуитивно понятный вопрос, поэтому вполне разумно думать, что P против NP более подходит в качестве отправной точки. По сути, я думаю, что проблема не в математике, а в том, как построенные нами математические модели вычислений соответствуют реальному миру и что в нем можно сделать.
Каве
1
NPcoNPPNP
1

ϕϕ

Тинниям Шринивасан Раманатха
источник
8
За исключением того, что мы знаем, что если бы физические законы не препятствовали созданию машин Блюма-Шуб-Смейла в нашей вселенной, P и NP были бы эквивалентны. Таким образом, вопрос будет связан с физическим миром , в этом смысле.
Кайл Джонс
@KyleJones Извините, я не понимаю, что вы говорите (возможно, потому что я недостаточно знаю о модели BSS). Не могли бы вы дать мне ссылку, которая объясняет это более подробно?
Тонниям Шринивасан Раманатха
Я имел в виду, что если получено математическое доказательство этого утверждения, никакие доказательства из физического мира не смогут его опровергнуть.
Тонниям Шринивасан Раманатха
-4

Вы можете провести множество экспериментов на скоростях и скоростях, и вы получите неопровержимые доказательства, подтверждающие законы Ньютона. Конечно, вы увидите некоторые очень странные вещи в очень специфических экспериментах, такие как скорость света в движущейся воде или некоторые астрономические события. Но ваши убедительные доказательства скажут вам: Ньютон прав, и эти законы - то, что вам нужно.

Конечно, Ньютон «не прав», и Эйнштейн последовал за ним.

Для P = NP мы можем видеть множество примеров, где кажется, что P ≠ NP. Но в некоторых частных случаях у нас есть странные вещи. Если P ≠ NP, существует бесконечное число классов между ними, поэтому мы должны найти некоторые проблемы в NP, которые не находятся в P, но не являются NP-полными. Мы не знаем ни одного из них, и большинство кандидатов оказались в P.

Что вы думаете об этой проблеме, зависит от того, куда вы хотите посмотреть. Я не удивлюсь, если P = NP.

Xoff
источник
7
На самом деле, все еще есть много кандидатов для NP-промежуточных задач, чья сложность остается нерешенной: cstheory.stackexchange.com/questions/79/…
Джошуа
этот список полезно знать, спасибо за этот комментарий!
Xoff