Диссертация (1137435), страница 8
Текст из файла (страница 8)
Тогда не может быть подмножествомни одного объектного содержания K. С учетом того, что квазизамкнутоследует, что ∩ ′ замкнуто для любого ∈ . Заметим, что ∈ посколь′. Рассмотрим ∩′ . Так как ∩′ замкнуто и ∈ ∩′ ,ку иначе ⊆ то возможны только два варианта: ∩ ′ = либо ∩ ′ = ′ . Допустим ∩ ′ = ′ . Тогда = ′ ∪ , где ⊂ {1 , ¬1 , . . . , , ¬ } и ̸= ∅′= {1 , . . . , } ∪ .(потому, что ̸= и ̸= ′ ). Рассмотрим ∩ Это множество должно быть замкнуто т.к.
квазизамкнуто. Заметим, что{1 , . . . , } ∪ * ′ , для всех 1 ≤ ≤ и {1 , . . . , } ∪ * ′ (т.к.′ ̸= ∅). Следовательно ( ∩ )′ ⊆ {1 , ¬1 , . . . , , ¬ }. Поскольку′( ∩ )′ ̸= ∅, то найдется литерал ∈ {1 , ¬1 , . . . , , ¬ } такой, что′ ∈ ( ∩ )′ . Тогда, по определению ′ и поскольку некоторая дизъ′юнкция содержит литерал мы получаем, что ∈/ ∩ . Таким′образом ∩ ′ = и ∖ {} = ∩ ⊆ {1 , ¬1 , . . . , , ¬ }. Болеетого, * ′ для каждого 1 ≤ ≤ , поскольку назначение = ∖{}(корректно) определено. В виду того, что ∖ {} замкнуто и по Лемме 1,назначение выполняет .2В [76, 78] было показано, что ∈ coNP следовательно мы получаемСледствие 1. Задача PI co -полна.542.5.Лектически максимальные псевдосодержания и перечисление максимальных псевдосодержанийВажная задача связанная с псевдосодержаниями это задача опреде-ления является ли данное множество лектически максимальным псевдосодержанием.Пусть = {1 , .
. . , } будет конечным линейно упорядоченныммножеством (1 < · · · < ). Для пары множеств ⊆ и ⊆ мыбудем говорить, что лектически меньше, чем ( < , лектическибольше чем ), если ∃ ∈ ∖ : ∩ { ∈ | < } = ∩ { ∈ | < }. Не сложно понять, что лектический порядок является линейномпорядком на подмножествах множества .Задача 3. Распознавание лектически максимального псевдосодержания(LLPI)ВХОД: Контекст K = (, , ) с линейным порядком на и подмножество ⊆ .ВОПРОС: Является ли лектически максимальным псевдосодержаниемконтекста K?Утверждение 2. Задача LLPI co -трудна.Доказательство. Мы сведем SAT к дополнению задачи LLPI так же какв Теореме 5. Линейный порядок на определим как: < 1 < .
. . < <1 < ¬1 < . . . < < ¬ < . Поскольку = ∖ {} и замкнуто, лектически максимальное псевдосодержание тогда и только тогда, когда является псевдосодержанием.2Таким образом, невозможно найти лектически максимальное псевдосодер-55жание за полиномиальное время, если ̸= .В [38, 39] было показано, что псевдосодержания не могут быть перечислены с полиномиальной задержкой в лектическом порядке (если ̸= ). Утверждение 2 показывает, что псевдосодержания нельзя перечислить с полиномиальной задержкой и в обратом лектическом порядке,т.е., мы получили следующее следствие.Следствие.
Псевдосодержания не могут быть перечислены с полиномиальной задержкой, если ̸= .Также в [38, 39] было показано, что невозможно найти все минимальные (по включению) псевдосодержания за полиномиальное от выхода время, если ̸= . Похожая задачу будет - задача перечисления максимальных (по включению) псевдосодержаний.Задача 4. Перечисление максимальных псевдосодержаний (EMPI)ВХОД: Контекст K = (, , )ВЫХОД: Все максимальные псевдосодержания контекста KУтверждение 3. Задача EMPI не может быть решена за полиномиальноеот выхода время, если ̸= .Доказательство.
Предположим мы можем решить EMPI за полиномиальное от выхода время. Рассмотрим произвольный вход задачи SAT исоответствующий ему контекст K = (, , ) из доказательства Теоремы 5. Заметим, что существует не более одного псевдосодержания, которое содержит , поскольку пересечение псевдосодержаний замкнуто, а непринадлежит ни одному содержанию кроме . Следовательно мы можемнайти псевдосодержание ⊆ ∖{} за полиномиальное время. Очевидно,56 ∖ {} является псевдосодержанием, если и только если = ∖ {}. 22.6.Распознавание существенных содержанийДругая задача связанная с задачей распознавания псевдосодержаний этозадача распознавания существенных содержаний.Задача 5. Распознавание существенного содержания (EI)ВХОД: Контекст K = (, , ) и множество ⊆ .ВОПРОС: Является ли существенным содержанием контекста K?Утверждение 4.
Задача EI NP-полна.Доказательство. 1. NP-трудность. Мы сведем SAT к EI, таким же образом как мы сводили SAT, к дополнению PI. Давайте построим контекстK2 = (, ∖ {}, ), где , и множество объектов, множество признаков и отношение контекста K из доказательства Теоремы 5 (см. Таблицу2.1). Очевидно, ∖ {} является существенным содержанием контекстаK2 тогда и только тогда, когда ∖ {} не является псевдосодержаниемконтекста K.2.
Принадлежность классу NP. Множество является существеннымсодержанием контекста K = (, , ) тогда и только тогда, когда существует псевдосодержание ⊆ такое, что ′′ = . Поскольку псевдосодержания это максимальные по включение квазизамкнутые множествас одинаковым замыканием (см. [76]), множество – существенное содержание, если и только если существует квазизамкнутое множество ⊆ такое, что ′′ = .
Квазизамкнутость может быть проверена за полиномиальное время (см. [41, 76, 78]). Следовательно свидетелем(доказательством)57того, что является существенным содержанием может быть квазизамкнутое множество такое, что ′′ = .2.6.1.2.Посылка импликации из минимального базисаМы доказали, что задача распознавания посылки импликации из особого минимального базиса (а именно базиса Дюкена-Гига) coNP-полна.Рассмотрим задачу распознавания посылки импликации из произвольногоминимального базиса. Пусть K = (, , ) – формальный контекст и пустьJ – произвольный минимальный базис импликаций контекста K. ПосколькуJ – минимальный базис импликаций контекста K, то для любой импликации → ∈ J множество является псевдосодержанием контекста K,где (·) – оператор квазизамыкания.
Рассмотрим следующую задачуЗадача 6. Распознавание посылки импликации из минимального базиса(PMB)ВХОД: Контекст K = (, , ) и множество ⊆ .ВОПРОС: Существует ли минимальный базис импликаций J контекста Kтакой, что → ∈ J для некоторого ?Поскольку задача распознавания псевдосодержания лежит в и квазизамыкания возможно вычислять за полиномиальное время, задачаPMB также лежит в . Теперь рассмотрим вход (K = (, , ), ) изсведения из доказательства Теоремы 5. Если квазизамыкание множества является псевдосодержанием, то тоже является псевдосодержанием,потому, что = или = , и – не псевдосодержание. Следовательно, если – посылка импликации из некоторого минимального базисаконтекста K, то – псевдосодержание контекста K. Если не существует58ни одного минимального базиса контекста K с импликацией с посылкой , то не может быть псевдосодержанием. Таким образом, мы доказалиследующе утверждениеУтверждение 5.
Задача PMB coNP-полна.Поскольку импликации формального контекста эквивалентны функциоанальным зависимостям (как показано выше), мы получаем следующееСледствие. Пусть дано – отношение базы данных с реляционной схемой и подмножество ⊆ . Задача разрешения – существует ли такоеминимальное покрытие функциональных зависимостей J, что → ∈ Jдля некоторого ⊆ coNP-полна.Задача 7. Генерация случайного псевдосодержания (RSP)ВХОД: Контекст K = (, , ).ВЫХОД: Псевдосодержание контекста K такое, что было выбранослучайно с ненулевой вероятностью среди всех псевдосодержаний контекста K.Допустим существует полиномиальный алгоритм , который можетгенерировать случайное псевдосодержание, т.е., выдавать псевдосодержание с ненулевой вероятностью для любого псевдосодержания контекста K.Тогда для любого псевдосодержания контекста K, существует ненулеваявероятность быть сгенерированным.
Рассмотрим произвольное псевдосодержание и случай когда наш алгоритм выдает это псевдосодержание . Мы можем записать все случайные шаги алгоритма и представить ихкак последовательность . Отметим, что || полиномиальна т.к. полиномиален. Теперь рассмотрим следующий алгоритм (, ), который прове-59ряет является ли псевдосодержанием, используя свидетеля . Алгоритм запускает алгоритм используя случайные операции записанные в и если выданное множество совпадает с , то он возвращает ответ ДА,иначе от возвращает ответ НЕТ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
