2004-gre-cs-practice-book.pdf/Q62 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q62-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q62-4c9f66 == | == Вопрос: Q62-4c9f66 == | ||
| − | < | + | Какие из следующих задач решаются за полиномиальное время, при общепринятой гипотезе <m>P \ne NP</m>? |
| − | + | ||
| − | + | # Дана [https://en.wikipedia.org/wiki/Combinational_logic логическая схема] с ''n'' входами и ''m'' выходами и <m>n^2</m> вентилями, где каждый вентиль является либо ''AND'', ''OR'', или ''NOT'', и заданы ''m'' значений <m>c_1,...,c_m</m> в качестве выходных данных или определяют, что <m>c_1,...,c_m</m> не является возможным выходным сигналом схемы | |
| − | + | # Учитывая ''n'' на ''n'' матриц ''A'' с рациональными числовыми элементами, либо найдите точное значение, обратное <m>A^{-1}</m> для ''A'', либо определите, что <m>A^{-1}</m> не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел ''a/b'' (<m>b \ne 0</m>), где ''a'' и ''b'' выражены в двоичной системе счисления) | |
| + | # Задан ориентированный граф с узлами, пронумерованными <m>1,2,...,n</m>, и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла ''n'', либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре) | ||
=== Ответы === | === Ответы === | ||
| − | + | * Только 1 | |
| − | + | * Только 2 | |
| + | * Только 3 | ||
| + | * 1 и 2 | ||
| + | * Правильный ответ: 2 и 3 | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|41|62}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | * 1 — Circuit-SAT, NPC | |
| − | + | * Обратную матрицу посчитать — полно полиномиальных алгоритмов, в школе проходили как через детерминант на худой конец. | |
| − | + | * Любой алгоритм для кратчайших путей максимум куб по времени. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 06:33, 16 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Теория сложности]] | |
Текущая версия на 06:33, 16 декабря 2024
Вопрос: Q62-4c9f66
Какие из следующих задач решаются за полиномиальное время, при общепринятой гипотезе ?
- Дана логическая схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
- Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
- Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)
Ответы
- Только 1
- Только 2
- Только 3
- 1 и 2
- Правильный ответ: 2 и 3
Объяснение
Исходники — вопрос 62 на 41 странице книги «2004-gre-cs-practice-book.pdf»
- 1 — Circuit-SAT, NPC
- Обратную матрицу посчитать — полно полиномиальных алгоритмов, в школе проходили как через детерминант на худой конец.
- Любой алгоритм для кратчайших путей максимум куб по времени.