1/ par induction sur la taille du mot et listage exhaustif des "petits" mots, tu dois pouvoir montrer ça., non ?
euh soudainement là...
n = 0, |x| = 0, <= c log(0)...
log(0)... ça marche pas ça ! Donc un tel x n'existe pas ! Les hypothèses sont fausses, on passe à la question suivante :D
2/ |y|, c'est log(nb_lettres(y))
log(|y|); c'est log(log((nb_lettres(y)))
montrer qu'on peut pas avoir <= c (log(log (nb_lettres(y)))
Hum.. pareil.. le mot vide. le log est pas défini dessus... (enfin, si le mot vide appartient à la fermeture par l'étoile de Kleene, je sais plus)
3/ Pareil que ribwund :D
4/ idem
Moi j'avais eu une preuve de NP-complétude d'un problème de graphes...
[^] # Re: 1 et 2
Posté par Axioplase ıɥs∀ (site web personnel) . En réponse au journal Oral d'informatique. Évalué à 1.
euh soudainement là...
n = 0, |x| = 0, <= c log(0)...
log(0)... ça marche pas ça ! Donc un tel x n'existe pas ! Les hypothèses sont fausses, on passe à la question suivante :D
2/ |y|, c'est log(nb_lettres(y))
log(|y|); c'est log(log((nb_lettres(y)))
montrer qu'on peut pas avoir <= c (log(log (nb_lettres(y)))
Hum.. pareil.. le mot vide. le log est pas défini dessus... (enfin, si le mot vide appartient à la fermeture par l'étoile de Kleene, je sais plus)
3/ Pareil que ribwund :D
4/ idem
Moi j'avais eu une preuve de NP-complétude d'un problème de graphes...