Discussion :

[mensoif]

Bonsoir,

je me retrouve dans la situation où j'ai choisi cette matière [Théorie de la complexité] et ce en allemand..

Bonsoir,

je suis actuellement en train de suivre un cours sur la théorie de la complexité (en allemand .. )

Et à vrai dire je me retrouve avec un poly. blindé de formule de lemme de définition de corolaire etc. Mais je ne sais que trop en faire ..
Il n'y a pas d'explications à proprement parlé, juste des énumérations de théorèmes (accompagnés des preuves respectives) etc.

Je me retrouve par exemple avec des définitions tel que :


(je n'arrive pas à lire, je comprends les symboles, mais ça s'arrête là)


J'aimerais donc trouver des cours d'explication, (mais pas trop vulgarisé non plus) en français.

J'ai déjà écumé pas mal de site d'université sans grand succés..

Merci bien.

Mens.

[Aleph69]

Bonsoir,

le sujet est plutôt vaste alors je ne sais pas trop ce dont tu as besoin. Peut-être trouveras-tu ton bonheur dans les cours en ligne du MIT? J'ai trouvé ça en faisant une recherche rapide :
http://ocw.mit.edu/courses/mathemati...lecture-notes/

[mensoif]

oui, j'aurais du préciser cela. Je me rattrape :

Les principales parties qui m'intéressent sont : la hiérarchie polynomiale ( avec oracle Turing machine.. ) et les classes de complexités probabilistes (BPP, probabiliste turing machine .. ).

Et lorsque je consulte les cours du MIT, je me retrouve avec le même genre d'info que j'ai dans mon poly, cad, une suite de théorème/déf/lemme qui me paraissent un peu trouble et c'est là dessus que j'aurais aimé un supplément d'info autre.

Voyez vous ce que je veux dire ?

[souviron34]

et Wiki et les lines associés ??

http://en.wikipedia.org/wiki/Computational_complexity

[mensoif]

et Wiki et les lines associés ??

à vrai dire, ça me ramène toujours sur des liens, qui sont soit un aperçu soit une énumération des défs.

Je commence à penser que ce que je cherche n'existe pas. Ce qu'il me reste à faire je pense, est donc de déchiffrer les défs (voir premier post).

Si vous pouvez m'aider pour celle là, et j'aviserais pour le reste:


Il s'agit de la définition de la hiérarchie polynomiale (source : http://en.wikipedia.org/wiki/Polynomial_hierarchy )


signification de L et p

// L be a language (i.e. a decision problem, a subset of {0,1}*)
pour moi lorsque je vois {0,1}* , je pense que cela fait référence aux réponses, cad, 0 -> non ; 1 -> oui, mais {0,1}* ? l'étoile ne signifie pas, on enlève 0 à cette ensemble ? dans ce cas où est le sens ?

// p un polynome

Une traduction donnerait (?)

Pour aux moins 1 polynome p du langage L nous avons une équivalence logique (:=) avec /*en plusieurs étapes */

{x} € {0,1}* : x serait une pair de string binaire ( gné ? )

le pipe : tel que ( http://en.wikipedia.org/wiki/Table_o...atical_symbolsv)

ensuite w serait un juste une unité de string binaire ( gné ? )²

puis vient cette ensemble et la réduction .. bref, je suis déjà largué ..

Merci d'avance si vous pouvez expliquer quelque chose là dedans.

[pseudocode]

Regarde si ce livre ne pourrait pas t'être utile : "Computational Complexity: A Modern Approach"

(on en trouve des extraits sur le Net)

[mensoif]

j'ai trouvé un draft et donc jeté un oeil, plus particulièrement sur la partie "poynomial hierarchie" mais je me retrouve toujours avec ces définitions mathématique. normal pour un tel livre je sais, mais hélas non accessible pour moi...

je réitère ma demande du dernier post, en effet, je retrouve souvent cette "forme" et je pense que si j'arrive à en lire une, les autres me seront plus accessibles !

un peu comme certains hiéroglyphe ?

[souviron34]

et dans les liens donnés dans cette page http://blog.computationalcomplexity....uters-and.html

tu ne trouves rien qui t'écalire ?

[Aleph69]

Bonsoir,

je ne peux pas vraiment t'aider à traduire le formalisme de cette théorie car je ne le connais pas. Le document suivant me semble toutefois tout à fait pertinent pour ton problème pour sa complétude et sa rigueur :
http://www.enseignement.polytechniqu.../poly-good.pdf
J'ai rapidement jeter un oeil au document et les notations semblent toutes avoir été introduites par son auteur.
Le chapitre 13 concerne les hiérarchies polynomiales mais la lecture de chapitres précédents est a priori nécessaire.
J'espère que ça te sera utile et bonne lecture!

[pseudocode]

je réitère ma demande du dernier post, en effet, je retrouve souvent cette "forme" et je pense que si j'arrive à en lire une, les autres me seront plus accessibles !

un peu comme certains hiéroglyphe ?

C'est l'analogue d'une hierarchie arithmétique, mais pour les polynomes (= pour les clauses d'un problème SAT).

Ce qui est curieux c'est la manière dont c'est défini par wikipedia. Je trouve ca plus clair en alternant les quantifieurs "Pour Tout" et "Il existe". On se rend mieux compte de l'inclusion.

[Acrim]

à vrai dire, ça me ramène toujours sur des liens, qui sont soit un aperçu soit une énumération des défs.

Je commence à penser que ce que je cherche n'existe pas. Ce qu'il me reste à faire je pense, est donc de déchiffrer les défs (voir premier post).

Si vous pouvez m'aider pour celle là, et j'aviserais pour le reste:


Il s'agit de la définition de la hiérarchie polynomiale (source : http://en.wikipedia.org/wiki/Polynomial_hierarchy )


signification de L et p

// L be a language (i.e. a decision problem, a subset of {0,1}*)
pour moi lorsque je vois {0,1}* , je pense que cela fait référence aux réponses, cad, 0 -> non ; 1 -> oui, mais {0,1}* ? l'étoile ne signifie pas, on enlève 0 à cette ensemble ? dans ce cas où est le sens ?

Si mes souvenirs sont bons, dans le contexte des langages formels il faut lire {0,1}^n comme l'ensemble des mots de taille n formés à partir de l'alphabet {0,1}. * correspond aux mot de taille quelconque.

Et |x| le nombre de lettre du mot x.

[mensoif]

Tout d'abord désolé pour le retard, j'étais indisponible hier..

et dans les liens donnés dans cette page http://blog.computationalcomplexity....uters-and.html

tu ne trouves rien qui t'écalire ?

non, en général, les résultats correspondent à ce que je trouve sur le google, cad intro ou formule de bourin (bien que je n'ai pas fait tout les liens) mais merci.

Le document suivant me semble toutefois tout à fait pertinent pour ton problème pour sa complétude et sa rigueur :
http://www.enseignement.polytechniqu.../poly-good.pdf
J'ai rapidement jeter un oeil au document et les notations semblent toutes avoir été introduites par son auteur.

oui, ce poly me plait bien, il ya des choses intéressantes, mais quelques concepts qui me sont encore flou, j'y reviendrais.

C'est l'analogue d'une hierarchie arithmétique, mais pour les polynomes (= pour les clauses d'un problème SAT).

Ce qui est curieux c'est la manière dont c'est défini par wikipedia. Je trouve ca plus clair en alternant les quantifieurs "Pour Tout" et "Il existe". On se rend mieux compte de l'inclusion.

SAT, il faut que je regarde ce que c'est.. par contre, je ne vois pas ce que tu reproches à wikipédia, les quantifieurs sont bien séparés, un par définition !

source : http://en.wikipedia.org/wiki/Polynomial_hierarchy
-> Definition 2;

Si mes souvenirs sont bons, dans le contexte des langages formels il faut lire {0,1}^n comme l'ensemble des mots de taille n formés à partir de l'alphabet {0,1}. * correspond aux mot de taille quelconque.

Et |x| le nombre de lettre du mot x.

Alors pour cette écriture, je l'ai découverte dans l'annexe du bouquin (en faite merci à pseudocode) "Computational Complexity: A Modern Approach"
et c'est ok, mais que vient faire l'inclusion à la place de l'étoile par la suite ? :o

Merci encore à tous !

[pseudocode]

SAT, il faut que je regarde ce que c'est.. par contre, je ne vois pas ce que tu reproches à wikipédia, les quantifieurs sont bien séparés, un par définition !

source : http://en.wikipedia.org/wiki/Polynomial_hierarchy
-> Definition 2;

C'est juste que je trouve plus simple cette définition là:

For every i>=1, a language L is in Σ(i,p) if there exists a polynomial-time TM M and a polynomial q such that :

x ∈ L <=> ∃u1∈{0,1}^q(x), ∀u2∈{0,1}^q(x), ∃u3... such as M(x,u1,u2,u3...)=1

L'alternance des quantifieurs ∃ et ∀ est plus visible.

[mensoif]

ah oui en effet, je n'avais même pas remarqué qu'il y avait une différence, d'ailleurs il n'y en a pas si je me réfère simplement à la définition donné par wikipedia. En effet, dans Définition 2; on retrouve la même définition avec juste "pour tout" et "il existe" d’inter-changé.

Tu peux m'en dire plus sur cette différence ? enfin, sur cette définition ? pourquoi n'y a t'il plus cette réduction ?

Je sais je dois commencer à être ch**** mais tout cela est vraiment obscur pour moi ...

[pseudocode]

ah oui en effet, je n'avais même pas remarqué qu'il y avait une différence, d'ailleurs il n'y en a pas si je me réfère simplement à la définition donné par wikipedia. En effet, dans Définition 2; on retrouve la même définition avec juste "pour tout" et "il existe" d’inter-changé.

Tu peux m'en dire plus sur cette différence ? enfin, sur cette définition ? pourquoi n'y a t'il plus cette réduction ?

Je sais je dois commencer à être ch**** mais tout cela est vraiment obscur pour moi ...

A mon sens, c'est la meme définition avec deux points de vue différents.

Celle de wikipedia dit que x est dans "∃pL" (un sous ensemble de L) s'il existe une preuve "w" que <x,w> soit dans L. Bref, "∃pL" est l'ensemble des éléments x qui sont solutions du problème.

Celle que j'ai donné dit que "L" est un langage Σ(i,p) si tous les éléments x de L vérifient le problème. Bref, ce "L" particulier est l'ensemble des éléments x qui sont solutions du problème.

[mensoif]

je reviens à la charge pour le signe de somme, cela fait plusieurs fois que je tombe sur Σ*, dans le contexte; un langage L ⊂ Σ* est dans *classe de complexité* si blablabla

Deplus, pour pseudocode, tu utilises la notation Σ(i,p) que signifie telle ?

Il doit certainement y avoir un rapport.

Merci !

[pseudocode]

je reviens à la charge pour le signe de somme, cela fait plusieurs fois que je tombe sur Σ*, dans le contexte; un langage L ⊂ Σ* est dans *classe de complexité* si blablabla

Deplus, pour pseudocode, tu utilises la notation Σ(i,p) que signifie telle ?

Il doit certainement y avoir un rapport.

Merci !

C'est la notation utilisée pour les "alternating Turing machine". L'exposant est le nombre d'alternance.

Je pense que si tu veux capter quelque chose aux documents que tu es entrain de lire, il faut commencer par comprendre dans l'ordre ce qu'est :
- une machine de Turing
- un probleme de classe P, NP, co-NP
- une machine de Turing "alternée"

C'est à mon avis la base pour comprendre pourquoi on fait une "hierarchie" en alternant les "il existe" et les "pour tout".

[mensoif]

Pour ce qui est d'une machine de Turing; oui c'est ok.

Pour les problèmes appartenant aux classes P, NP, et coNP, si je dis juste:

- P : problème de décision qui peut être résolu sur une machine déterministe en temps polynomial par rapport à la taille de donné (soit une complexité O(1),O(n) ou O(nk) exposant k par exemple)
est ce que 3 est pair ? réponse non

- NP : problème de décision qui peut être résolu sur une machine non-déterministe) en temps polynomial. Soit déterminer (via une NTM) en temps exponentiel (EXPTIME) les propositions de solution puis vérifier en temps polynomial si les réponses sont "yes" ou "no" (dans le cas de coNP).

ex: recherche de cycle hamiltonien ? ce que je ne suis pas, c'est que l'on classe ce problème en NP-complet, alors qu'il est possible de faire : déterminer propositions de solutions (exptime) puis vérification des solutions(ptime)..

En ce qui concerne la ATM, je ne fais pas trop la différence une NTM, (une histoire de règles pour NP , coNP) je pense que j'en ai pas besoin pour le moment. (du moins je n'en ai pas encore rencontré) Par contre je pense que t'as réflexion sur les ATM concernait principalement Σ(i,p), car désormais je pense avoir compris Σ* en tant que mot de taille quelconque de l'alphabet d'un problème de décision.

Par conte une machine qui est pas mal présente est l'oracle turing machine, j'ai compris le fonctionnement, et je me suis rendus compte que l'on utilise une OTM (enfin plutôt les réductions polynomial) pour définir la hiérarchie polynomial, ce qui me choque. La hiérarchie polynomial est donc basé sur une "facilité logique" complétement abstraite du genre Psat = Pnp .

[pseudocode]

ex: recherche de cycle hamiltonien ? ce que je ne suis pas, c'est que l'on classe ce problème en NP-complet, alors qu'il est possible de faire : déterminer propositions de solutions (exptime) puis vérification des solutions(ptime)..

Je ne sais pas ce qui te choque. C'est exactement la définition que tu as donné d'un problème NP.

Par contre je pense que t'as réflexion sur les ATM concernait principalement Σ(i,p), car désormais je pense avoir compris Σ* en tant que mot de taille quelconque de l'alphabet d'un problème de décision.

Ok. Je parlais effectivement de Σ(i,p).

Par conte une machine qui est pas mal présente est l'oracle turing machine, j'ai compris le fonctionnement, et je me suis rendus compte que l'on utilise une OTM (enfin plutôt les réductions polynomial) pour définir la hiérarchie polynomial, ce qui me choque. La hiérarchie polynomial est donc basé sur une "facilité logique" complétement abstraite du genre Psat = Pnp .

Pas loin.

Σ(2,p) = NP^NP
Σ(3,p) = (NP^NP)^NP
...

Tu peux lire le chapitre 5.5 (Defining the hierarchy via oracle machines, remark 5.15) du bouquin dont j'ai parlé sur ce sujet.