2004-gre-cs-practice-book.pdf/Q62

Вопрос: Q62-4c9f66

Какие из следующих задач решаются за полиномиальное время, при общепринятой гипотезе ?

Дана логическая схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)

Исходники — вопрос 62 на 41 странице книги «2004-gre-cs-practice-book.pdf»

1 — Circuit-SAT, NPC
Обратную матрицу посчитать — полно полиномиальных алгоритмов, в школе проходили как через детерминант на худой конец.
Любой алгоритм для кратчайших путей максимум куб по времени.

(нет элементов)

Войдите, чтобы комментировать.