Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Полиномиальные сведения и NP-полные задачи
СообщениеДобавлено: 29 сен 2019, 20:17 
Не в сети
Начинающий
Зарегистрирован:
29 сен 2019, 20:12
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Первая задача: существует ли означивание переменных заданной 3-КНФ, при котором в каждой скобке окажется хотя бы один истинный и хотя бы один ложный литерал?
Вторая задача: существует ли в заданном неориентированном графе (без весов) разрез, размер которого не менее заданного числа?
Докажите, что первая задача полиномиально сводима ко второй.

Для доказательства NP-полноты можно использовать NP-полноту следующих задач: 1) выполнимость булевой формулы (SAT); 2) выполнимость 3-КНФ; 3) существование клики заданного размера в графе; 4) существование вершинного покрытия заданного размера в графе; 5) наличие гамильтонова пути в ориентированном графе.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ 1 сообщение ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задача на полиномиальные события

в форуме Теория вероятностей

Fantlk

7

536

18 ноя 2020, 15:18

Полиномиальные уравнения степени 3

в форуме Алгебра

Integrator

2

349

14 май 2015, 07:04

Решить с помощью сведения к дифф. уравнению

в форуме Интегральное исчисление

Azerot

1

335

10 фев 2016, 20:00

Полные системы

в форуме Дискретная математика, Теория множеств и Логика

luckyboyr

2

177

13 сен 2021, 21:08

Про частные и полные производные

в форуме Дифференциальное исчисление

Yurij-97

1

418

01 июн 2017, 19:45

Найти полные дифференциалы функций

в форуме Дифференциальное исчисление

Ciber15

9

600

14 фев 2018, 10:12

Найти полные дифференциалы функций

в форуме Дифференциальное исчисление

Jakci

1

298

22 фев 2018, 14:10

Тем, кто сразу дает полные решения

в форуме Размышления по поводу и без

venjar

100

2413

06 апр 2019, 19:45

Найти все полные свертки тензора

в форуме Линейная и Абстрактная алгебра

mwstw9

2

194

03 июн 2023, 16:19

Полные решетки. Теорема о неподвижной точке

в форуме Дискретная математика, Теория множеств и Логика

Ramil987

2

171

21 ноя 2022, 14:17


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved