Тема: Недетерминированная сложность подсчета числа совершенных паросочетаний в графе
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
📋 Содержание
2 Определения и используемые результаты 3
3 Формулировка основных результатов 4
4 Верхняя оценка для задачи 0-1 перманент 4
4.1 Необходимые формулы 5
4.2 Описание алгоритма 5
4.3 Анализ 6
5 Построение недетерминированного алгоритма с помощью арифметических схем 6
6 Построение сведений к многочленам 7
6.1 Задача о покрытии множества 7
6.2 Задача о подсчете гамильтоновых циклов 9
6.3 Задача 0-1 перманент 10
Список литературы 12
📖 Введение
Также в статье [3] была введена следующая гипотеза:
Гипотеза 1. Nondeterministic Strong Exponential Time Hypothesis (NSETH) Для любого e > 0 существует такое k, что k-TAUT ^ NTIME(2ra(1-€)), где k-TAUT - язык формул, являющихся тавтологиями в дизъюнктивной нормальной форме, в которых в каждом клозе ровно k литералов.
В [3] было показано, что отрицание гипотезы 1 влечет нижние оценки на несколько классов булевых схем. Если же гипотеза 1 верна, то к задачам, для которых существуют достаточно быстрые как недетерминированные, так и конедетерминированные алгоритмы, не существует эффективных fine-grained сведений от задачи SAT.
Мы же покажем, что из нижних оценок на конедетерминированную сложность задач 0-1 перманент, о покрытии множества и о подсчете гамильтоновых циклов в графе следуют нижние оценки на арифметические схемы. Также приведем верхнюю оценку для задачи 0-1 перманент.
✅ Заключение
📕 Список литературы
🖼 Скриншоты
