Предположим, что П=НП. То есть любая проблема, решение которой можно быстро проверить, также может быть быстро решена, независимо от того, что это означает на формальном уровне. Значит, не только П=НП, но существуют практические полиномиальные алгоритмы для НП- полные проблемы. Кроме того, доказательство либо конструктивно, либо неконструктивно. То есть можно найти алгоритм, который мы в конечном итоге найдем достаточно быстрым, чтобы начать использовать его, даже если мы не сможем его доказать. Тогда становится намного труднее хранить секреты — огромная проблема. Меня пугает не наша неспособность скрыть информацию, а наша неспособность раскрыть ее.
В сложном обществе нам нужно доверять другим, а того, что мы можем проверить самостоятельно, недостаточно. На практике мы устанавливаем доверие к учреждениям, когда они неоднократно предоставляют нам точную информацию. Я не вижу альтернативного метода, поэтому, если мы потеряем возможность проверить, что получаем информацию от конкретного учреждения, то самозванец может воспользоваться нашим доверием, чего нельзя допускать. Следовательно, мы не можем быть достаточно хорошо информированы, чтобы иметь сложное общество. П=НП разрушит текущую аутентификацию и, следовательно, создаст фундаментальный риск, если не будут найдены другие решения.
Можно ли найти другие решения?
Если П=НП, у нас есть мир без конфиденциальности, но, сократив наши потери в этом отношении, мы могли бы попытаться построить аутентификацию вокруг этого факта. Вместо того, чтобы сущности давали нам информацию, необходимую для их идентификации, мы могли бы просто выжать ее из них. Одна из идей состоит в том, что после получения сообщения мы отправляем наше сообщение, содержащее некоторую информацию, которая будет отправлена нам вместе с исходным сообщением, чтобы мы знали, что наше сообщение было получено и что получатель, по крайней мере, хотел отправить исходное сообщение. сообщение. Наше сообщение — шпионское ПО, усиленное нашим эффективным алгоритмом для НП-полные задачи, которые мы используем для проверки источника исходного сообщения.