Qu'est-ce que la classe de complexité

Que signifie la classe de complexité ? Je sais que est la classe de complexité qui contient les langages pour lesquels il existe une machine de Turing polynomiale à temps non déterministe telle que si le nombre d'états accepteurs de la machine sur l'entrée est impair. $\oplus P^{\oplus P}$ $\oplus P$ $A$ $M$ $x \in A$ $M$ $x$

Mais que signifie ? Je ne peux tout simplement pas suivre ce qu'il fait réellement :) $\oplus P^{\oplus P}$

Quelles sont les conséquences pratiques d'une telle classe de complexité et comment peut-on montrer que ? $\oplus P^{\oplus P} = \oplus P$

complexity-theory terminology complexity-classes stewenson
la source

Cette notation (à mon humble avis) dénote des classes de complexité relative ou oracle. Voir Wikipedia pour une définition. Est-ce que cela répond à la question? Sinon, veuillez modifier pour clarifier.

Raphaël

Vous trouverez la preuve de

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

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

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

sdcvvc

Réponses:

désigne la classe équipée de ce qu'on appelle unoraclepour - nous disons qu'il a été donné la possibilité de déterminer si une chaîne appartientou non àun langage contenu dans la classe en une seule opération. $\oplus P^{\oplus P}$ $\oplus P$ $\oplus P$ $s$ $L$ $\oplus P$

Je vois qu'un autre commentateur (sdcwc) a lié à la preuve de (voir ces notes sur une conférence du CS 538 à Rutgers ). Une classe de complexité qui est un oracle à une classe telle que , est dit être faible pour la classe . Dans ce cas, nous disons que est faible pour lui-même. $\oplus P^{\oplus P} = \oplus P$ $C$ $B$ $B^C= B$ $B$ $\oplus P$

Josh Lockhart
la source

Un autre lien pour vous, cette fois vers la page wikipédia sur le 'lowness' des classes de complexité: en.wikipedia.org/wiki/Low_%28complexity%29

Josh Lockhart

Votre style d'explication est suffisant pour comprendre les principes de base et il est facile à suivre.

stewenson

Que voulez-vous dire essentiellement que

est équipé de l'oracle qui peut déterminer l'appartenance à la langue

en une seule étape? De mon point de vue, si vous voulez résoudre un problème dans

, vous interrogez l'oracle au tout début du calcul, donc après la première étape, vous savez comment l'oracle vous répond? Donc, vous savez que puisque vous avez atteint un état d'acceptation, le nombre de ces états n'est qu'un, donc le nombre impair, alors vous acceptez?

\oplus P

$\oplus P$

L

$L$

\oplus P^{\oplus P}

$\oplus P^{\oplus P}$

stewenson

\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$

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$

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$