Mengapa P dan P / poly tidak sama?

Definisi P adalah bahasa yang dapat diputuskan oleh algoritma waktu polinomial. Definisi P / poli dapat diartikan sebagai bahasa yang dapat diputuskan oleh sirkuit ukuran polinomial (lihat http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Sekarang, mengapa sirkuit ukuran polinomial tidak dapat disimulasikan dalam waktu polinomial?

Intinya tentang rangkaian adalah bahwa rangkaian memiliki jumlah input yang tetap. Ini berarti bahwa, untuk mendefinisikan suatu bahasa, kita memerlukan rangkaian keluarga sedemikian rupa sehingga sirkuit  memberi tahu Anda string panjang mana  berada dalam bahasa, untuk setiap  . Ini tidak mengharuskan bahwa harus ada hubungan antara sirkuit dan  : mereka bisa sangat berbeda. Secara khusus, untuk setiap set  , Anda bisa mengatur declare jika dan untuk . Bahkan jika$C_0, C_1, C_2, \dots$$C_i$$i$$i$$C_i$$C_{i+1}$$S\subseteq\mathbb{N}$$C_i=\mathrm{true}$$i\in S$$C_i=\mathrm{false}$$i\notin S$$S$ tidak dapat diputuskan!

Sebaliknya, sebuah bahasa ada di  jika ada mesin Turing tunggal yang memberi tahu Anda apakah setiap input yang mungkin dari setiap panjang yang mungkin ada dalam bahasa. Sekarang, Anda tidak dapat memainkan game lucu tentang input dengan panjang berbeda.$\mathrm{P}$

Anda benar bahwa kami dapat mengevaluasi sirkuit tetap apa pun di  . Tapi itu belum cukup untuk memutuskan bahasa di . Untuk melakukan itu, pertama-tama kita perlu menghitung panjang input, kemudian menggunakannya untuk menentukan sirkuit  perlu kita evaluasi, dan kemudian mengevaluasi sirkuit. Seperti yang ditunjukkan contoh di atas, bagian "tentukan sirkuit mana" mungkin bahkan tidak dapat dihitung, apalagi yang dapat dihitung dalam waktu polinomial.$\mathrm{P}$$\mathrm{P/poly}$$C_i$