Семинар Добрушинской лаборатории @ВШМ МФТИ

Create: 2025-04-27 Update: 2025-07-09 05:14:15

Семинар Добрушинской лаборатории

Когда: вторник 29 апреля, 16:15
Где: Адм. корпус, ауд.322.

Доклад:

Дарья Серова, Михаил Рыбаков (Тверской ГУ и МФТИ),
"NP-полнота задачи разбиения множества"

Задача разбиения множества (Partition) имеет очень простую формулировку, но является NP-полной. Формулировка задачи следующая: по (мульти)множеству А натуральных чисел требуется выяснить, можно ли разбить А на два подмножества с одинаковыми суммами элементов. Эту задачу можно сформулировать и как оптимизационную: для (мульти)множества А найти такое его разбиение на два подмножества, при котором модуль разности сумм элементов этих подмножеств является наименьшей из возможных.

В докладе будет показано простое доказательство NP-полноты (прежде всего, NP-трудности) задачи Partition. Для этого будет построено полиномиальное сведение к ней задачи SubsetSum (состоящей в том, что нужно установить для числового множества А и числа Т, имеется ли в А подмножество с суммой элементов, равной Т), к которой мы полиномиально сведем проблему CNF (проблему выполнимости булевых формул, находящихся в конъюнктивной нормальной форме). В оставшееся время мы докажем NP-трудность проблемы CNF, полиномиально сведя к ней проблему SAT (проблему выполнимости булевых формул в полном языке), а затем докажем NP-трудность проблемы SAT, используя идею классического доказательства Кука–Левина.

Планируется интернет-трансляция по адресу:
https://telemost.yandex.ru/j/81255480783695
Регистрируйтесь вашей фамилией, а не псевдонимом!

Страницы семинара:
https://sites.google.com/view/dobr-seminar
https://www.mathnet.ru/conf167

Адрес: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Вход в МФТИ только по пропускам или спискам. Поэтому участники БЕЗ пропусков МФТИ пришлите ЗАРАНЕЕ (до понедельника) информацию о себе и не забудьте паспорт.

ВШМ МФТИ

❤‍🔥5❤2🔥1🤨1

hottg.com/mipt_math/102

920 viewsApr 27 at 07:08

>>Click here to continue<<

ВШМ МФТИ

Share with your best friend

United States America Popular Telegram Group (US)

Telegram Q&A

Q: How does hottg.com work?

Once you've set up a username, you can give people a hottg.com/username link. Opening that link on their phone will automatically fire up their Telegram app and open a chat with you. You can share username links with friends, write them on business cards or put them up on your website.This way people can contact you on Telegram without knowing your phone number.

With Telegram, you can send messages, photos, videos and files of any type (doc, zip, mp3, etc), as well as create groups for up to 200,000 people or channels for broadcasting to unlimited audiences. You can write to your phone contacts and find people by their usernames. As a result, Telegram is like SMS and email combined — and can take care of all your personal or business messaging needs. In addition to this, we support end-to-end encrypted voice calls.

Q: What is Telegram? What do I do here?

Telegram is a messaging app with a focus on speed and security, it’s super-fast, simple and free. You can use Telegram on all your devices at the same time — your messages sync seamlessly across any number of your phones, tablets or computers.

Q: Who is Telegram for?

Telegram is for everyone who wants fast and reliable messaging and calls. Business users and small teams may like the large groups, usernames, desktop apps and powerful file sharing options. You can appoint admins with advanced tools to help these communities prosper in peace. Public groups can be joined by anyone and are powerful platforms for discussions and collecting feedback.In case you're more into pictures, Telegram has animated gif search, a state of the art photo editor, and an open sticker platform (find some cool stickers here or here). What's more, there is no need to worry about disk space on your device. With Telegram's cloud support and cache management options, Telegram can take up nearly zero space on your phone.

Q: How is Telegram different from WhatsApp?

Unlike WhatsApp, Telegram is a cloud-based messenger with seamless sync. As a result, you can access your messages from several devices at once, including tablets and computers, and share an unlimited number of photos, videos and files (doc, zip, mp3, etc.) of up to 2 GB each. And if you don't want to store all that data on your device, you can always keep it in the cloud.Thanks to our multi-data center infrastructure and encryption, Telegram is faster and way more secure. On top of that, Telegram is free and will stay free — no ads, no subscription fees, forever.

Q: Can I make calls via Telegram?

Yes! Voice calls are currently available to users around the world.

Many modern travelers appear to struggle with managing various aspects of their finances simultaneously while abroad, such as banking, budgeting, investing, trading, and saving. It is important to have apps installed on the device that will help you carry out these necessary tasks.

Hot Topic in US

Telegram Desktop App Not Working on Windows?

Семинар Добрушинской лаборатории