Perché un linguaggio polinomiale hanno un circuito polinomiale di dimensioni?

Question

Vorrei capire perché P è un sottoinsieme di PSCPACE, per questo un langauge tempo polinomiale non hanno un circuito polinomiale dimensioni. Ho letto molte prove, come questa qui a pagina 2-3 , ma tutte le prove utilizzare la stessa tecnica utilizzata nel Cook-Levin teorema per convertire il calcolo di M su un ingresso x n bit ad un circuito polinomio dimensioni.

Quello che non comprendo è che il circuito risultante dipende dalle x ingresso, perché ciò che viene convertito in un circuito è il calcolo della M sull'ingresso specifica x. Per definizione di pSize, lo stesso circuito deve lavorare per tutti gli ingressi in una lunghezza fissa, e quindi non dipende da un ingresso specifico.

Così come è il processo di creazione di una famiglia di circuiti di poli di dimensioni per una macchina di Turing deterministica poli-time funziona esattamente?

Answer 1

Cook-Levin dà un circuito per tutti gli ingressi di una determinata dimensione. Quindi, anche se il circuito dipende dall'ingresso $ x $, dipende solo dalla dimensione dell'input. Così dato TM $ M $ con esecuzione tempo $ t $, e un numero $ n $ (la dimensione di ingresso), Cook-Levin dà un circuito $ C_n $ di dimensioni approssimativamente $ t ^ 2 $ che risolve il problema su tutti gli ingressi di dimensioni $ n $. Il circuito di $ C_n $ non dipende da quali sono i bit del input per $ M $, ma abbiamo bisogno di sapere il numero di bit di ingresso come che sta per essere il numero di bit di ingresso per il circuito.

Answer 2

Intuitivamente, un polinomio esigenze problema dimensione almeno un circuito polinomio dimensioni perché ogni passo dell'algoritmo / circuito richiede una certa quantità di tempo. Se il circuito ha potuto verificare un elemento del linguaggio, in meno di un tempo polinomiale, quindi un algoritmo potrebbe essere fatto a fare altrettanto.