Сейчас осознал, что задача о потоке минимальной стоимости для случая когда стоимости ребер могут быть отрицательными — NP. Алгоритмы через путь минимальной стоимости не работают из-за отрицательных циклов, а теорема о том что поток имеет минимальную стоимость т.ит.т.к. нет отрицательных циклов для этого случая вообще не верна, хотя ошибка весьма неочевидна. Почему-то я об этом нигде раньше не встречал упоминаний.
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.09.2024 03:44:38 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Почему не слышали, что задача в классе NP? Ответ: это очевидно. Но она ещё и лежит в классе P. Есть семейство алгоритмов, которые выбирают отрицательный цикл и пускают по нему поток, некоторые из которых строго полиномиальны. Легко гуглится по словам min mean-cost cycle cancelling.
Я писал, что мне показалось, что это метод вообще неправильный. Но я уже нашел ошибку в своем контрпримере. Теперь опять ничего не понимаю. То есть, у меня как бы есть доказательство P=NP и я уже 3 часа не могу найти в нем ошибку. Теперь буду искать завтра с утра.
Вы свели какую-нибудь NP-hard задачу к потоку минимальной стоимости? Или что вы подразумеваете под словом доказательство?
Ура. Таки P!=NP?, по крайней мере пока. Ошибка была в неверном понимании потока. Интуитивно, когда дают задачу о потоке говорят, допустим, о системе трубопроводов по которым с минимальной стоимостью надо перекачать что-то из начального пункта в конечный. При этом неявно предполагается, что это что-то есть только в начальном пункте и изначально нигде его больше нет. Так вот, в такой формулировке задача NP-полна. Когда же речь идет о цикруляции, то предполагается, что эти трубопроводы уже как-то заполнены, даже если граф несвязный. Тогда полиномиально.