Преобразования в XOR конъюнктивной форму

Question

XOR конъюнктивной формы определяются следующим образом: (а исключающее б) и (с исключающим д) ... и т.д.

и СБ-XCF это язык определяется прецедент (исключающей ИЛИ конъюнктивные) выражения, которые являются выполнимыми.

Я хотел бы знать, что SAT-XCF является NP трудным? Таким образом, существует ли функция, способная преобразовать любое выполнимое булево выражение в выполнимую XOR-конъюнктивную форму?

Большое спасибо за ваш вклад.

Answer 1

Я думаю, что ответ на ваш последний вопрос «нет» даже для двух переменных. В частности, (a OR b) не может быть представлено как И любого количества выражений XOR. Существует очень мало различных выражений XOR для двух переменных: false, true, a, b,! A,! B (a XOR b) и (a XOR! B). Если вы И с любым из них: false, true, a, b,! A,! B, (a XOR b), (a XOR! B), вы установите ложную одну из 4 возможных комбинаций (a, б). Это оставляет только выражение true, которое отличается от (a OR b).