Расширение шаблона спецификаций на основе LINQ для реализации погружения

Question

Расширение шаблона спецификаций на основе LINQ для реализации погружения

Существует много реализаций шаблона составной спецификации на основе LINQ. Я не видел тот, который использовал Subsuration.

Существуют ли такие примеры, которые были задокументированы (блоги и т. Д.) Или опубликованы с открытым исходным кодом? У меня есть идея и подтверждение концепции того, как это может работать, когда ExpressionVisitor переводит каждую спецификацию в каноническую логическую форму (CNF/DNF), но я обеспокоен тем, что это слишком сложно. Есть ли способ лучше?

4

linq boolean-logic boolean-expression linq-expressions specification-pattern

Источник

user344211 04 дек '12 в 23:12

1 ответ

Решение

Другие вопросы по тегам linq boolean-logic boolean-expression linq-expressions specification-pattern

user335858 11 дек '12 в 20:12 2012-12-11 20:12 · Accepted Answer · 2012-12-11 20:12

Я обеспокоен тем, что это слишком сложно. Есть ли способ лучше?

Краткий ответ: "Нет, нет" ¹

Длинный ответ: "чрезмерно сложный" отражает суть проблемы: это NP-сложный. Вот краткое неформальное доказательство, основанное на том факте, что проблема выполнимости является NP-полной:

Предположим, что у вас есть две логические формулы, A а также B
Вам нужно проверить, если A подразумевает B или эквивалентно ¬A | B для всех назначений переменных, по которым A а также B зависят. Другими словами, вам нужно доказательство того, что F = ¬A | B это тавтология.
Предположим, что тавтологический тест может быть выполнен за полиномиальное время
Рассматривать ¬F обратная F, F выполнимо тогда и только тогда, когда ¬F это не тавтология
Используйте гипотетический полиномиальный алгоритм для проверки ¬F за тавтологию
Ответ на это F выполнимо "является обратным ответом на" является ¬F тавтология "
Следовательно, наличие полиномиальной проверки тавтологии означало бы, что проблема выполнимости находится в P и что P=NP,

Конечно, тот факт, что проблема является NP-трудной, не означает, что не было бы решений для практических случаев: фактически, ваш подход с преобразованием в каноническую форму может дать хорошие результаты во многих реальных ситуациях. Однако отсутствие известного "хорошего" алгоритма часто препятствует активной разработке практических решений ².

¹ с обязательным P=NP "отказ от ответственности.

² Если "разумно хорошее" решение не подойдет, что вполне может иметь место для вашей проблемы, если вы допустите "ложные негативы".