Использование недетерминизма для обнаружения клик?

Question

Я пытаюсь понять недетерминизм с проблемой клики.

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

Скажем, у меня есть график с узлами A, B, C, D, E, F и я хочу решить, существует ли клика из 4.

Мое понимание недетерминированности заключается в том, чтобы сделать предположение, взяв четыре узла (B, C, D, F) и проверить, существует ли соединение между всеми четырьмя узлами. Если он существует, я делаю вывод, что существует клика, а если нет, я заключу, что клики не существует.

Что я не уверен в том, как это помогает решить проблему, поскольку я просто мог сделать неправильный выбор.

Я предполагаю, что я пытаюсь понять применение недетерминизма вообще.

Answer 1

Недетерминированный выбор отличается от случайного или произвольного выбора. При использовании недетерминизма, если любой возможный выбор, который можно сделать, приведет к выходу алгоритма YES, тогда будет выбран один из этих вариантов. Если нет выбора, который сделает это, тогда будет сделан произвольный выбор.

Если это похоже на обман, то оно есть. Неизвестно, как эффективно реализовать недетерминизм с использованием детерминированного компьютера, рандомизированного алгоритма или параллельных компьютеров с множеством процессоров, но которые могут выполнять лишь небольшую работу по каждому ядру. Это вопросы P = NP, BPP = NP и NC = NP соответственно. Соответственно, недетерминизм - это прежде всего теоретический подход к решению проблем.

Надеюсь, это поможет!