Co to jest klasa złożoności

Co oznacza klasa złożoności ? Wiem, że jest klasą złożoności, która zawiera języki dla których istnieje wielomianowa niedeterministyczna maszyna Turinga taka, że iff liczba akceptujących stanów maszyny na wejściu jest nieparzysta. $\oplus P^{\oplus P}$ $\oplus P$ $A$ $M$ $x \in A$ $M$ $x$

Ale co oznacza ? Po prostu nie mogę śledzić, co faktycznie robi :) $\oplus P^{\oplus P}$

Jakie są praktyczne konsekwencje takiej klasy złożoności i jak można wykazać, że ? $\oplus P^{\oplus P} = \oplus P$

complexity-theory terminology complexity-classes

— Stewenson
źródło

Ten (imho niezręczny) zapis oznacza klasy złożoności względnej lub wyroczni. Zobacz Wikipedii dla definicji. Czy to odpowiada na pytanie? Jeśli nie, edytuj, aby wyjaśnić.

— Raphael

Dowód

na cs.rutgers.edu/~allender/538/murata3.pdf

\oplus P^{\oplus P} = \oplus P

$\oplus P^{\oplus P} = \oplus P$

— sdcvvc

oznacza klasę wyposażoną w tak zwanąwyroczniędla - mówimy, że dano jej możliwość ustalenia, czy łańcuch jest członkiem języka zawartego w klasie w jednej operacji. $\oplus P^{\oplus P}$ $\oplus P$ $\oplus P$ $s$ $L$ $\oplus P$

Widzę, że inny komentator (sdcwc) został połączony z dowodem (patrz te notatki na wykładzie z CS 538 na Rutgers ). Klasa złożoność to wyrocznią do klasy tak, że , mówi się, że niska dla klasy . W tym przypadku mówimy, że jest dla siebie niski. $\oplus P^{\oplus P} = \oplus P$ $C$ $B$ $B^C= B$ $B$ $\oplus P$

— Josh Lockhart
źródło

Kolejny link, tym razem do strony wikipedii na temat „lowness” klas złożoności: en.wikipedia.org/wiki/Low_%28complexity%29

— Josh Lockhart

Twój styl wyjaśnienia jest wystarczający do zrozumienia podstawowych zasad i jest łatwy do naśladowania.

— stewenson

Co w zasadzie masz na myśli

że

jest wyposażony w wyrocznię, która może określić przynależność do języka

w jednym kroku? Z mojego punktu widzenia, jeśli chcesz rozwiązać jakiś problem w

, przeszukujesz wyrocznię na samym początku obliczeń, więc po pierwszym kroku wiesz, jak wyrocznia odpowiada? Więc wiesz, że skoro osiągnąłeś jeden stan akceptacji, liczba takich stanów jest tylko jeden, więc liczba nieparzysta, więc akceptujesz?

\oplus P

$\oplus P$

L

$L$

\oplus P^{\oplus P}

$\oplus P^{\oplus P}$

— stewenson

„ wyrocznia dla

- mówimy, że dano jej możliwość ustalenia, czy język

jest członkiem

w jednej operacji.” - jest to błędne: Wyrocznia daje możliwość określenia, czy dany ciąg

jest członkiem jakiegoś języka

. Bez utraty ogólności,

można uznać za

(ponieważ jest to

\oplus P

$\oplus P$

L

$L$

\oplus P

$\oplus P$

s

$s$

L

$L$

\oplus P

$\oplus P$

L

$L$

\oplus S A T

$\oplus SAT$

\oplus P

$\oplus P$

— kompletne

Staram się bardzo mocno podążać za dowodem, ale dla mnie jest to zupełnie niejasne. Na przykład, co oznacza funkcja

? Wiem, że jest to „powtórz 1 raz (

)”, ale do czego służy w tym kontekście? Co

myśli szczególnie

? A co z

wszędzie? Jeśli

, to

f (1^{i}, x)

$f(1^i,x)$

1^{3} = 111

$1^3 = 111$

1^{i}

$1^i$

k

$k$

n^{k}

$n^k$

i \leq n^{k}

$i \leq n^k$

. Co to znaczy? Dlaczego masz funkcję

z takim wejściem?

f (1^{i}, x) = f (1^{n^{k}}, x) = f (1^{| x |^{k}}, x)

$f(1^i,x) = f(1^{n^k}, x) = f(1^{|x|^k}, x)$

f \in ♯ P

$f \in \sharp P$

— stewenson