• Новости
• Блоги
• Аналитика
• Новости компаний
• В СНГ и в мире
• Анонсы

NP-complete?

01 июня 2009

В дискретной математике есть раздел, посвященный алгоритмизации. В данном разделе приводится классификация алгоритмов, где выделяются 3 основных класса сложности:

- P – полиномиальные – это задачи, время решения которых прямо пропорционально объему входных данных: сложение, умножение, взятие остатка от деления и т.п.

- NP – недетерминированные полиномиальные - это задачи, время решения которых существенно зависит от объема входных данных, но если существуют какие-то дополнительные сведения (свидетели решения), то решение может найтись достаточно быстро. Пример - нахождение квадратного корня числа, которое является квадратом простого числа.

- NP-полные задачи (NP-complete) – в отличие от NP не имеют свидетелей решения, поэтому найти ответ за полиномиальные сроки сейчас не представляется возможным. Задача коммивояжера – это наиболее яркий пример подобных задач, когда речь идет об отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. Еще один пример NP-complete – небезызвестная игра "Сапер".

А к чему я это все? А к тому, что в телекоме аббревиатура NP тоже существует и последние годы вызывает большое количество споров и разговоров. Я имею в виду, конечно же, Number Portability или свободный перенос телефонных номеров между операторами. Именно то, о чем мечтают многие абоненты, даже не подозревая всех подводных камней вокруг этого процесса, то, чего так боятся операторы, и то, что совсем неочевидно по своей полезности и необходимости.

Итак, для того, чтобы найти решение задачи, нужно для начала определить, к какому классу задач можно отнести внедрение Number Portability? Для начала оценим объем входных данных: кто участвует в этой задаче, на ком она существенно отразится?

1) абонент с перемещаемым номером (которому это перемещение влетит в дополнительную копеечку, но он об этом еще не догадывается);

2) оператор – изначальный владелец номера;

3) оператор – новый "владелец" номера;

4) клиринговый центр, учитывающий перемещения номерных емкостей;

5)  государство, как регулятор;

6) абоненты, звонящие абоненту с перемещаемым номером (вот сюрприз будет для них, когда они, получив счет, поймут, что звоня на местный номер, оплачивают его, как звонок на мобильный, или звоня на зоновый мобильный, получат междугородный счет);

7)  сторонние операторы, маршрутизирующие свой трафик абонентам с перемещаемыми номерами;

8) вендоры биллинговых систем, учитывающие маршрутизацию трафика на перемещенные номера.

Теперь попробуем найти свидетелей решения - вдруг удастся решить задачу относительно просто?

Кто у нас есть из свидетелей, уже прошедших эту операцию:

– Сингапур (не подходит по масштабу);

– Испания (не подходит по масштабу);

– Швейцария (не подходит по масштабу);

– Может, США? Масштаб вроде подходящий - протяженность линий связи, разнородность систем связи и т.п. Может, этот пример послужит достойным свидетелем? Но, увы, и он тоже не подходит. Услуга NP стала следствием масштабной реформы телеком-отрасли, проведенной в США после знаменитого Телекоммуникационного Акта 1996-го года. К тому времени американский телеком-рынок был одним из самых развитых. Он пережил тяжелый кризис 80-х годов, а перед завершением внедрения Number Portability и не менее тяжелый "крах доткомов", который особенно больно ударил по высокотехнологичным стартапам. Этот рынок слишком другой, он формировался эволюционно десятки лет, здесь большую роль играют кабельные компании, велика дифференциация операторов по функциональному назначению (магистральники, операторы последней мили, операторы последнего дюйма, кабельные и т.п.). Телекоммуникационный Акт 1996-го года позволил объединить ингридиенты этой солянки и урегулировать взаимоотношения между операторами, что позволило существенно сократить время провизионинга и активации услуг на межоператорском уровне.

Резюмирую: можно отбросить все 21 настоящих свидетеля. Может быть, правда, 22-й (Индия), который должен появиться через год, поможет? Кто знает, пока нашу задачу стоит отнести к классу NP-Complete, так может стоит все-таки подождать квантовых компьютеров, ведь, как предполагается, именно они смогут решать NP-полные задачи эффективно?

Оставить свой комментарий:

Комментарии по материалу