Почему на языке полиномиального времени есть схема полиномиального размера?

Question

Я хотел бы понять, почему P является подмножеством PSCPace, поэтому в Langauge полиномиального времени есть схема полиномиального размера. Я прочитал много доказательств, таких как этот здесь, на странице 2-3, но все доказательства используют ту же метод, который использовался в теореме Кука-Левина, чтобы преобразовать вычисление М на n-битном входе X в схему полиномиального размера.

Чего я не понимаю, так это то, что результирующая схема зависит от входа X, потому что то, что преобразуется в схему, является вычислением M на конкретном входе X. По определению PSIZE, одна и та же схема должна работать для всех входов в фиксированной длине, и, следовательно, не зависит от одного конкретного входа.

Так как же работает процесс создания семейства схем поли-размера для полити-времени-детерминированной машины Тьюринга?

Answer 1

Кук-Левин дает одну схему для всех входов данного размера. Таким образом, хотя схема зависит от входного $ x $, она зависит только от размера ввода. Таким образом, учитывая TM $ M $ с временем выполнения $ T $, и число $ n $ (размер ввода), Cook-Levin дает схему $ C_N $ размером примерно $ t^2 $, которая решает проблему на всех входах размера $ n $. Схема $ c_n $ не зависит от того, что является битами ввода для $ m $, однако нам нужно знать количество входных бит, так как это будет количество входных бит для схемы.

Answer 2

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