Dlaczego P i P / poli nie są takie same?

Definicja P jest językiem, o którym decyduje algorytm wielomianowy. Definicja P / poly może być rozumiana jako język, który może być ustalony przez obwód wielkości wielomianowej (patrz http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Dlaczego więc nie można symulować obwodu wielomianowego w czasie wielomianowym?

Chodzi o to, że obwody mają stałą liczbę wejść. Oznacza to, że do zdefiniowania języka potrzebujemy rodziny obwodów$C_0, C_1, C_2, \dots$ taki, że obwód $C_i$ mówi ci, które ciągi długości $i$ są w każdym języku $i$. Nie wymaga to żadnego związku między obwodami$C_i$ i $C_{i+1}$: mogą być zupełnie inne. W szczególności dla każdego zestawu $S\subseteq\mathbb{N}$, możesz ustawić deklaruj $C_i=\mathrm{true}$ gdyby $i\in S$ i $C_i=\mathrm{false}$ dla $i\notin S$. Nawet jeśli$S$ jest nierozstrzygalny!

Natomiast język jest w $\mathrm{P}$jeśli istnieje jedna maszyna Turinga, która powie ci, czy każde możliwe wprowadzenie każdej możliwej długości jest w języku. Teraz nie możesz grać w śmieszne gry o wejściach o różnej długości.

Masz rację, że możemy ocenić dowolny obwód stały $\mathrm{P}$. Ale to niekoniecznie wystarcza do wyboru języka$\mathrm{P/poly}$. Aby to zrobić, musielibyśmy najpierw obliczyć długość wejścia, a następnie użyć tego do ustalenia, który obwód $C_i$musimy ocenić, a następnie ocenić obwód. Jak pokazuje powyższy przykład, część „określ, który obwód” może nawet nie być obliczalna, a tym bardziej obliczalna w czasie wielomianowym.