Bonjour,

petite présentation rapide, je suis actuellement étudiant en informatique, m1, et j'étudie la théorie de la complexité (vous savez toutes les jolies classes genre P, NP, BPP etc.).

Et donc, c'est cette matière qui m'amène à vous !

J'ai déjà un peu feuilleté avec la fonction recherché, hormis quelques clarifications sur les classes P/NP ou NP/NPC je n'ai pas trouvé grand chose.

J'ai plusieurs style de questions dans le genre :
- montré que NP ⊆ PP, RP ⊆ BPP ce genre de chose
déjà rien qu'en voyant la question je trouve ça étrange, pour RP⊆BPP je veux bien(bien que ne sachant pas comment le faire) puisqu'il s'agit tout deux de classe de complexité basé sur des machines de turing probabilistes, mais pour NP⊆PP on a de la machine de turing déterministre et de la PTM.. à moins que ça n'ait aucun rapport.

- il y a aussi ce genre d'inclusions qui met en jeu des machines de turing avec oracle (OTM)
P exposant (RP) ⊆ RP exposant (RP) = RP.

Bref, que des joyeusetés. Si je pouvais obtenir quelques axes/explications ce serait super.

Merci