4.2. Упрощение задачи

Вследствие особой природы ЗНП часто удается сделать при ее исследовании определенные, хорошо известные заранее выводы и упрощения [6, 26, 27, 28, 30, 50, 51].

Например:

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

(2) если такое, что то должно присутствовать во всех решениях и задачу можно свести к «меньшей», положив

(3) пусть тогда если такие, что то можно удалить из поскольку любое множество, которое покрывает должно также покрывать т. е. доминирует над

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

Предположим, что все эти упрощения выполнены (если они возможны) и что исходная ЗНП уже переформулирована в соответствующей неприводимой форме.