Составители:
Рубрика:
Все переборные задачи (без направленного перебора) относят-
ся к NP -сложным задачам. В классе NP -сложных задач выявлены
универсальные, к которым полиномиально сводятся любые задачи
из некоторых классов. Если бы удалось доказать, что универсаль-
ная задача имеет полиномиальную сложность, то тем самым было
бы доказано, что все задачи соответствующего класса имеют поли-
номиальную сложность.
3.2. О сужении класса задач
Среди рассмотренных выше задач имеются N P -сложные. Рас-
смотрим следующую задачу: для двух данных графов G
1
= (V
1
, E
1
)
и G
2
= (V
2
, E
2
) требуется указать, можно ли получить из графа G
1
граф G
2
с помощью операции простого гомоморфизма. Эта зада-
ча является NP-сложной даже в простейших случаях (например,
когда граф G
2
представляет собой треугольник).
Следовательно, нет никаких оснований надеяться на то, что
можно получить решение общей задачи отображения графов ал-
горитмов на архитектуру вычислительных систем с помощью уни-
версального метода.
Причина этой ситуации кроется в том, что класс рассматрива-
емых алгоритмов слишком широк; сузить же этот класс трудно по
двум причинам: 1) недостаточно ясно, какие алгоритмы необходимо
включить в этот класс (ибо мы плохо представляем те задачи, ко-
торые собираемся решать), 2) трудно дать удобную формализацию
интересующего нас класса. Заметим еще, что сужая класс рассмат-
риваемых алгоритмов, нужно следить за тем, чтобы не выбросить
интересующие нас алгоритмы.
Таким образом, NP -сложность задачи о "гомоморфизме
графов" связана с излишне большим количеством рассматрива-
емых ситуаций.
96
Страницы
- « первая
- ‹ предыдущая
- …
- 93
- 94
- 95
- 96
- 97
- …
- следующая ›
- последняя »
