NP-полные задачи в k-значной логике

romanenkoroman1

У кого-нибудь есть список?
"Search the web" просьба не предлагать, уже безуспешно пытался

Nonnik

Wikipedia

romanenkoroman1

и её смотрел. Именно к-значная нужна, а её там нет

Nonnik

А книжку саму эту смотрел?
Garey and Johnson's seminal book Computers and Intractability: A Guide to the Theory of NP-Completeness.
Может, там чё ещё пишут.

CokpaT

С ходу мне кажется, что вряд ли в к-значной логике будут какие-то принципиально новые задачи по сравнению с двузначной. Просто те же самые задачи можно решать и в к-значной логике (задачу о выполнимости КНФ и всякие ее разновидности).

Dallas

Не совсем так. Например, при k>=3 NP-полна задача 2-выполнимость, которая при k=2 полиномиальна.

Lokomotiv59

Прошу прощения за тупость, но что вообще такое "задача в k-значной логике" ?
Задачи с графами - в какой логике например ?

Dallas

Задачи в k-значной логике - это задачи о функциях k-значной логики.
Задачи с графами - это задачи с графами.

romanenkoroman1

Не совсем так. Например, при k>=3 NP-полна задача 2-выполнимость, которая при k=2 полиномиальна.

А можно ссыслочку на доказательство? Мне как раз примерно такие вещи и нужны

Dallas

не знаю, где это есть
это типа фольклор
даже точную формулировку "2-выполнимости" не знаю
Хотя можно использовать такую:
есть формула, представляющая из себя конъюнкцию k-значных функций, принимающих булевы значения, зависящих от двух переменных; определить, выполнима она или нет.
К такой задаче элементарно сводится задача о правильной вершинной k-цветной раскраске графа.
Можно взять более узкую формулировку: функции только вида (x != a || y != b). Эта тоже NP-полна.
А если рассматривать функции вида (x == a || y == b то такая задача будет полиномиальна.

Dallas

Есть ещё статья Алексеев, Носов "NP-полные задачи и их полиномиальные варианты". Раньше в инете была, сейчас не знаю (недавно пытался где-нибудь скачать, не смог).
Возможно, там есть про k-значную логику (хотя точно сказать не могу).

romanenkoroman1

Статью я наверно смогу достать. Если тебе ещё нужна - вышлю, как найду.
Раз уж ты рюхаешь в этом, более общий вопрос.
Сама задача такая: есть схема функциональных эл-тов с единственным выходом. Базисные функции - все функции к-значной логики от <=n пер-нных (n- небольшая константа, например, 5). f- реализуемая этой схемой ф-ция. Пусть f(0, ...., 0)=0. Нужно найти минимальный по модулю вектор аргументов, при котором она не равна 0.
Понятно, что в таком виде она NP-полна (понятно, в переформулировке: для данного l, cуществует ли вектор длины <=l и т.д.). Нужно найти ограничения на базисные ф-ции(можно, например, считать их монотонными) и структуру схемы (например, можно, чтобы схема была устроена "по слоям" чтобы были полиномиальные (по сложности схемы) алгоритмы. Я пока нашёл только тривиальный случай, когда граф этой схемы - дерево. Надо бы найти что-нибудь, чтобы одна переменная в схеме (и вообще, любой эл-т схемы) могла несколько раз использоваться. И именно для к-значного случая.
Идеи какие-нибудь есть?

Dallas

Статью я наверно смогу достать. Если тебе ещё нужна - вышлю, как найду.
О! Круто! Хорошо бы...
Сама задача такая: есть схема функциональных эл-тов с единственным выходом. Базисные функции - все функции к-значной логики от <=n пер-нных (n- небольшая константа, например, 5). f- реализуемая этой схемой ф-ция. Пусть f(0, ...., 0)=0. Нужно найти минимальный по модулю вектор аргументов, при котором она не равна 0.
Понятно, что в таком виде она NP-полна (понятно, в переформулировке: для данного l, cуществует ли вектор длины <=l и т.д.). Нужно найти ограничения на базисные ф-ции(можно, например, считать их монотонными) и структуру схемы (например, можно, чтобы схема была устроена "по слоям" чтобы были полиномиальные (по сложности схемы) алгоритмы. Я пока нашёл только тривиальный случай, когда граф этой схемы - дерево. Надо бы найти что-нибудь, чтобы одна переменная в схеме (и вообще, любой эл-т схемы) могла несколько раз использоваться. И именно для к-значного случая.
Интуиция подсказывает, что задача хреновая. Для монотонных элементов задача NP-полна даже в двузначной логике. Более того, она NP-полна для схем глубины 2 из элементов && и || (с неограниченным количеством входов к ней легко сводится задача о покрытии.
Не знаю, что даст ограничение "по слоям". Но, скорее всего, ничего. Потому что на таких схемах моделируют машину Тьюринга (при этом её моделируют на схемах, где каждый элемент связан только с "близко расположенными" элементами соседних слоёв!). Т.е. без ограничений на функциональные элементы такая задача NP-полна даже в двузначной логике. Что будет, если наложить ограничение на ФЭ, я не знаю.
Задача может быть полиномиальной, если для неё работает динамическое программирование. Пока приходят в голову только различные модификации на тему деревьев.

Dallas

Ещё NP-полный вариант. Двузначная логика. Есть 3 схемы - дерева A, B, C из монотонных элементов. Окончательная схема - A&B&C.
Для двух деревьев, думаю, та же хрень (только доказать не могу).

Lokomotiv59

Задачи с графами - это задачи с графами.
Ты не прав, чтобы такое утверждать надо четко дать описание того, что тебе нужно, какая логика имеется ввиду и тп. Думаешь нельзя выразить какое-нибудь утверждение из теории графов в терминах k-значной логики, используя кванторы ?

romanenkoroman1

Интуиция подсказывает, что задача хреновая. Для монотонных элементов задача NP-полна даже в двузначной логике. Более того, она NP-полна для схем глубины 2 из элементов && и || (с неограниченным количеством входов к ней легко сводится задача о покрытии.

Сам вижу, что жопа, это я уже тоже получил Есть правда небольшая лазейка: покрытие вроде бы решается полиномиально, если каждый элемент лежит в <= 2 множествах. Т.е. для моей задачи, если у каждого эл-та <= 2 выходов, по крайней мере, можно сделать переход от слоя к слою. Это в 2-значной логике в базисе and/or. Но на k-значную ведь это не обобщается?
Задача может быть полиномиальной, если для неё работает динамическое программирование

Я тешу себя надеждой, что для послойной схемы как раз это и получится. Но похоже, что зря

Dallas

Ты не прав, чтобы такое утверждать надо четко дать описание того, что тебе нужно, какая логика имеется ввиду и тп. Думаешь нельзя выразить какое-нибудь утверждение из теории графов в терминах k-значной логики, используя кванторы ?
, логика у нас обычная, которая у Цермелы с Френкелем. Задачи про k-значную логику - это задачи, в формулировке которых есть слово "k-значная логика". Если их переформулировать в терминах графов или двузначной логики, то будут задачи про графы и двузначную логику. Гуманитарно всё короче, и придираться

Dallas

Сам вижу, что жопа, это я уже тоже получил Есть правда небольшая лазейка: покрытие вроде бы решается полиномиально, если каждый элемент лежит в <= 2 множествах. Т.е. для моей задачи, если у каждого эл-та <= 2 выходов, по крайней мере, можно сделать переход от слоя к слою. Это в 2-значной логике в базисе and/or. Но на k-значную ведь это не обобщается?
А что значит послойная схема? Схема, элементы которой можно разбить на слои так, чтобы каждый элемент i-го слоя был связан входами с элементами i-1 - го слоя (входы в нулевом слое)? Если так, то эта задача NP-полна даже для монотонных элементов в двузначной логике.

romanenkoroman1

А что значит послойная схема? Схема, элементы которой можно разбить на слои так, чтобы каждый элемент i-го слоя был связан входами с элементами i-1 - го слоя (входы в нулевом слое)?

Да
Если так, то эта задача NP-полна даже для монотонных элементов в двузначной логике.

В общем случае да, но см. предыдущий пост. Правда, пример с тремя деревьями ставит этот план под сомнение :/
Ну это то, до чего я успел дойти. Хочется просто найти какой-нибудь нетривиальный полиномиально-разрешимый случай, чтоб требования были естественными. Не найду - забабахаю генетический алгоритм (тем самым перейдя из физ-мат наук в технические )

Dallas

В общем случае да, но см. предыдущий пост
В смысле, про не более двух выходов у элементов? Выходы - это как я понимаю провода, соединяющие выход с другими элементами? Всё равно NP-полно всё получается, на двух выходах можно моделировать любое их количество.

romanenkoroman1

Смысл такой: рассмотрим такую 3-слойную схему:
0 слой - переменные
1 слой - дизъюнкции этих переменных (только пер-нных, без отрицаний)
2 слой - едиственный эл-т - конъюнкция всех этих дизъюнкций - выход схемы f
Задача найти минимальное число нунулевых пер-нных, делающих f равной 1 - эквивалентная переформулировка задачи о мин. покрытии, которая решается полиномиально, если каждый эл-т лежит в <=2 множествах (другой случай - каждое множество содержит <= 2 эл-тов - тут неинтересен). Для переформулировки это означает, что каждая переменная входит в <= 2 дизъюнкции. Это я и имел в виду под числом выходов. Как раз между 2 и 3 иногда и проходит грань между P и NPC

Dallas

Возможно, но тут думаю больше трёх слоёв не получится сделать (полиномиально)
Оставить комментарий
Имя или ник:
Комментарий: