Проблема со значением цепи
Проблема значения схемы (или проблема оценки схемы) — это вычислительная задача вычисления вывода заданной логической схемы на заданном входе.
Задача завершена для P при равномерном AC 0 сокращения. Обратите внимание, что с точки зрения временной сложности ее можно решить за линейное время просто с помощью топологической сортировки .
Проблема значения логической формулы (или проблема оценки логической формулы) — это частный случай проблемы, когда схема представляет собой дерево. решена. Задача о значении логической формулы для NC 1 . [1]
Проблема тесно связана с булевой проблемой выполнимости , которая является полной для NP , и ее дополнением, проблемой пропозициональной тавтологии , которая является полной для co-NP .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Сэмюэл Р. Басс (январь 1987 г.). «Проблема со значением логической формулы находится в ALOGTIME» . В Альфреде В. Ахо (ред.). Материалы 19-го ежегодного симпозиума ACM по теории вычислений (STOC) . АКМ. стр. 123–131. ( авторский вариант )
- Ричард Э. Ладнер (январь 1975 г.). «Проблема со значением схемы — пространство журнала заполнено для P». Новости ACM SIGACT . 7 (101): 18–20. дои : 10.1145/990518.990519 .
 | Эта компьютерному программированию, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |