Небульова монотонна проблема планарної схеми

Відомо, що монотонні планарні логічні схеми мають проблему значення контуру NC (фактично, багато більше відомо ).

А що стосується схем небулої монотонної планарної ?

Точніше, візьміть $ Q = \ (0, ..., n-1 \) $ і будь-яке сімейство монотонних функцій $ f_i: Q ^ 2 \ rightarrow Q $ і розглянемо планарні схеми, в яких ворота вибрані серед $ f_i $. Що таке схеми?

4
Я не думаю, що хтось вивчив цю проблему. Я думаю, що алгоритми MPCVP для бінарного випадку можна легко змінити, коли розмір Q постійний (шляхом створення більш детальної інтервальної структури). Проте, якщо Q дозволено змінюватися залежно від розміру вхідного матеріалу, здається, що проблема P завершена, маючи альтернативні рівні Q, що представляють істинну та хибну.
додано Автор caryden, джерело

Відповідей немає

0