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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




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

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

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

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

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

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

Integrator

2

254

14 май 2015, 07:04

Решить методом сведения к дифференциальному ур 2-го порядка

в форуме Дифференциальные и Интегральные уравнения

ZiggX

1

434

16 окт 2010, 09:28

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

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

Azerot

1

139

10 фев 2016, 20:00

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

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

Yurij-97

1

217

01 июн 2017, 19:45

Полные дифференциалы функции

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

egorkovv

1

379

21 янв 2013, 04:15

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

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

Ciber15

9

316

14 фев 2018, 10:12

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

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

Jakci

1

121

22 фев 2018, 14:10

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

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

venjar

96

1297

06 апр 2019, 19:45

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

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

ahgel1990

0

506

12 дек 2014, 02:25

Теория моделей, матлогика. Полные теории

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

Iv_Vol

1

263

25 дек 2016, 16:36


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



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

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


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

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

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

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