Pourquoi une langue polynomial ont un circuit polynôme de taille?

Question

Je veux comprendre pourquoi P est un sous-ensemble de PSCPACE, c'est pourquoi un langauge temps polynôme a un circuit polynôme de taille. Je lis beaucoup de preuves comme celui-ci ici à la page 2-3 , mais toutes les preuves utiliser la même technique utilisée dans le théorème de Cook-Levin pour convertir le calcul de M sur une entrée à n bits x à un circuit de taille polynomiale.

Ce que je ne comprends pas que le circuit résultant dépend des x d'entrée, parce que ce qui est converti en un circuit est le calcul de M sur l'entrée spécifique x. Par définition de PSIZE, le même circuit doit fonctionner pour toutes les entrées d'une longueur fixe, et ne dépend donc pas sur une entrée spécifique.

Alors, comment est le processus de création d'une famille de circuits poly moyenne pour une machine de Turing déterministe poly-temps fonctionne exactement?

Answer 1

Cook-Levin donne un circuit pour toutes les entrées d'une taille donnée. Ainsi, bien que le circuit dépend de la $ entrée x $, il ne dépend que de la taille de l'entrée. Donc, étant donné TM $ M $ avec le temps en cours d'exécution $ t $, et un numéro $ n $ (la taille de l'entrée), Cook-Levin donne un circuit $ C_n $ de taille à peu près t $ ^ 2 $ qui permet de résoudre le problème sur toutes les entrées de taille $ n $. Le circuit $ C_n $ ne dépend pas de ce que sont les bits de l'entrée pour $ M $, mais nous avons besoin de connaître le nombre de bits d'entrée comme cela va être le nombre de bits d'entrée pour le circuit.

Answer 2

Intuitivement, a besoin de problème de taille polynomiale au moins un circuit de taille polynomiale parce que chaque étape de l'algorithme / circuit nécessite un certain laps de temps. Si le circuit pourrait vérifier un élément de la langue en moins de temps polynomial, alors un algorithme pourrait être fait de le faire aussi.