Обнаружение схемы, которая похожа по функциональности и реализации

Пусть $x=(x_1,\dots,x_n)$ - вектор булевых переменных. Пусть $C,D$ две булевы схемы на $x$ . Скажите, что $C$ похож на $D$ если:

1. x { 0 , 1 } $\Pr[C(x) \ne D(x)]$$x$$\{0,1\}^n$

2. $C,D$ различаются по расстоянию редактирования графика незначительно (их расстояние редактирования намного меньше размера схемы, скажем, или некоторой небольшой константы), что означает, что почти все вентили и провода совпадают соответствующие ворота и провод в , с добавлением / удалением / изменением только нескольких ворот.C $O(1)$$C$$D$

Моя проблема: мне дана схема , и я хочу знать, существует ли схема которая похожа на но не идентична (т. Е. Там, где существует такой, что ).D C C x C ( x ) ≠ D ( x $C$$D$$C$$C$$x$$C(x)\ne D(x)$

Кто-нибудь может предложить алгоритм решения этой проблемы?

Если это помогает, мы можем ограничить внимание схемами , которые меньше, чем данная схема (т. Е. Мы хотим знать, существует ли схема такая, что меньше, чем , подобна , и существует такой, что ).C D D C D C x C ( x ) ≠ D ( x $D$$C$$D$$D$$C$$D$$C$$x$$C(x)\ne D(x)$

Если это помогает, вы можете дополнительно предположить, что нам даны хорошие тестовые примеры такие что для все , и мы можем далее ограничить внимание только схемами такими, что для всех . C ( x i ) = y i i D D ( x i ) = y i$x^1,\dots,x^m,y^1,\dots,y^m$$C(x^i)=y^i$$i$$D$$D(x^i)=y^i$$i$

Это вытекает из практического применения, поэтому, если вы не можете решить эту проблему, не стесняйтесь решать любой вариант или интересный особый случай. Например, не стесняйтесь создавать экземпляры любых параметров или порогов любым удобным для вас способом. Можно предположить, что схемы не слишком велики (полиномиального размера или что-то). Не стесняйтесь заменить расстояние редактирования графика каким-либо другим показателем, близким к реализации. Кроме того, на практике решатели SAT часто удивительно эффективны на структурированных схемах, возникающих на практике, поэтому, вероятно, хорошо вызывать решатель SAT в качестве подпрограммы / оракула (по крайней мере, если вы вызываете его на чем-то похожем на производный экземпляр SAT из цепи, как ).$C$

В качестве альтернативы, при отсутствии каких-либо алгоритмов меня также интересовал бы вопрос о существовании: для «средней» схемы , какова вероятность того, что существует некоторый который удовлетворяет всем критериям? (Я надеюсь, что эта вероятность очень мала, но я понятия не имею, так ли это).$C$$D$

Практическое применение состоит в том, чтобы проверить, может ли схема содержать вредоносный бэкдор / скрытое пасхальное яйцо. Гипотеза о том, как можно вставить такую ​​вещь, выглядит следующим образом. Мы начнем с «золотой» схемы , которая вычисляет желаемую функциональность и не имеет скрытого бэкдора. Затем противник делает небольшое изменение , чтобы ввести скрытый черный ход, получение модифицированной схемы . Цель бэкдора - каким-то образом изменить функцию, вычисляемуюЕсли не слишком мало, изменение может быть достоверно обнаружено при случайном тестировании, поэтому злоумышленник, вероятно, попытается сохранитьD D C D Pr [ C ( x ) ≠ D ( x ) ] Pr [ C ( x ) ≠ D ( x ) ] C D x i , y i D D ( x i ) = y i i C D C $C$$D$$D$$C$$D$$\Pr[C(x) \ne D(x)]$$\Pr[C(x) \ne D(x)]$очень маленький. Точно так же, если отличается от в слишком многих местах, это можно заметить при случайной проверке схемы, поэтому злоумышленник, вероятно, попытается свести к минимуму количество изменений. (И, может быть, есть набор тестов из пар которые представляют экземпляры желаемой функциональности, поэтому мы знаем, что, какой бы ни была «золотая» схема , она удовлетворяет для всех .) В конечном счете, нам дана схема (но не «золотая» схема ), и мы хотим знать, может ли быть модифицированной версией некоторого$C$$D$$x^i,y^i$$D$$D(x^i)=y^i$$i$$C$$D$$C$$D$где была сделана модификация для введения скрытого бэкдора такого рода.

Это только расширенный комментарий, который пришел мне в голову сразу после прочтения вопроса:

• Предположим, у вас есть формула 3SAT с переменными и пусть - соответствующая схема;п х 1 , . , , , х н$\phi$$n$$x_1,...,x_n$$C$

• построить новую схему , добавив переменных и достаточное количество входов в AND новых переменных с выходом исходного ( ); т = п к у 1 , у 2 , . , , , y n k m C C ′ = ϕ ∧ y 1 ∧ . , , ∧ у $C'$$m = n^k$$y_1, y_2, ...,y_{n^k}$$m$$C$$C' = \phi \land y_1 \land ... \land y_m$

• построить новую схему из которая просто принудительно выводит свой вывод в 0, используя логические элементы AND и NOT ( )C ′ D ′ = C ′ ∧ ¬ C $D'$$C'$$D' = C' \land \neg C'$

Если не выполнимо, то и эквивалентны, в противном случае они отличаются, когда удовлетворяет формуле И все , но вы можете выбрать достаточно большим, чтобы сделать вероятность того, что очень мала.D ' С ' х я у я = 1 м ⋀ у я = $\phi$$D'$$C'$$x_i$$y_i = 1$$m$$\bigwedge y_i = 1$

Поэтому, если у вас есть эффективный алгоритм для вашей задачи, вы можете эффективно решить экземпляр 3SAT.