(1) Я думаю, что автор имеет в виду, что проблема NP не была найдена, для которой доказано , что ее нет в P. Конечно, есть проблемы в NP, для которых не известно полиномиальное решение, но это не то же самое, что знать, что ничего не существует.
Если на самом деле P = NP (то есть, если на самом деле не существует NP-задач, не имеющих полиномиального решения), то вв некотором смысле недетерминированная машина не является «более мощной», чем детерминированная машина, поскольку они решают одни и те же проблемы за полиномиальное время.Тогда мы бы сказали, что «недетерминизм не является таким важным улучшением».
(2) Способ, которым доказательство n log n работает, состоит в том, что есть n! возможных выходов из функции сортировки, любой изкоторый может быть правильным в соответствии с порядком ввода. Каждое сравнение добавляет двуногую ветвь к дереву всех возможных состояний, в которые может попасть данный алгоритм сортировки сравнения.Чтобы отсортировать любые входные данные, это «дерево решений» должно иметь достаточно ветвей, чтобы произвести любое из n! возможных переупорядочений входных данных, и, следовательно, должно быть хотя бы log(n!) сравнение.Таким образом, нижняя граница времени выполнения зависит от размера дерева.
Автор говорит, что нет известных проблем NP, для которых мы доказали, что им требуется дерево, настолько большое, что оно подразумевает нижнюю границу.это супер-полином.Любое такое доказательство докажет P != NP.