Аннотация:
Рассматриваются понятия минимального сложного и граничного классов графов. Доказывается, что для задачи распознавания принадлежности наследственному классу графов не существует минимальных сложных классов. Указываются граничные и минимальные сложные классы графов для задач о списковом ранжировании. Эти классы графов являются первыми примерами минимальных сложных классов, а также первыми примерами сложных граничных классов. Библиогр. 9.
Ключевые слова:вычислительная сложность, минимальный сложный класс, граничный класс, распознавание наследственного свойства, задачи о списковом ранжировании.
УДК:519.178
Статья поступила: 10.04.2009 Переработанный вариант: 20.07.2009
Полный текст:
PDF файл (231 kB)