Discussion:L (complexité)
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Section de la classe SL
modifierJe suis dubitatif sur l'intérêt de définir encore aujourd'hui la classe SL, vu qu'elle correspond exactement à L. Je baptiserais plutôt cette section: "Exemple de problème, le problème USTCON" et enlèverais les références à SL. Ça convient?
PS: Pour être plus précis, je pense que la classe SL peut être intéressante si elle est définit à l'aide des machines symétriques, et l'on peut alors parler du résultat de Reingold qui prouva, grâce à USTCON que L=SL. Mais définir SL comme les problèmes que l'on peut réduire à USTCONN (un problème connu dans L) me semble contre-productif.Nietsabes (discuter) 11 janvier 2014 à 18:40 (CET)
- Bonjour, ça ne me semble pas si stupide : d'une part on cite les machines symétriques (si tu veux faire l'article fais toi plaisir...), d'autre part c'est intéressant d'un point de vue historique, on cite plus volontier le résultat comme "L=SL" qu'en passant par USTCON. En plus on peut imaginer un lecteur qui verrait SL quelque part et qui chercherait sur wikipedia... Donc à mon avis on peut le laisser, peut-être le modifier. (PS : il faut signer ses paroles sur les pages de discussion, ça se fait automatiquement en mettant 4 tildes, ou bien avec le petit crayon de la barre au-dessus)--Roll-Morton (discuter) 11 janvier 2014 à 17:23 (CET)
Voilà, j'ai modifié la définition, en insistant plus sur les machines symétriques. Si ça ne plait pas plus, je n'ai rien contre revenir à la version précédente. (PS : désolé de ne pas signer mes messages, je ne connaissais pas cette fonction "4 tildes. Merci.) Nietsabes (discuter) 11 janvier 2014 à 18:40 (CET)
Nietsabes : Réponse beaucoup plus tard : merci ! --Roll-Morton (discuter) 26 février 2015 à 21:02 (CET)
Nietsabes : J'approuve. C'est chouette. J'ai juste réécrit pour que ce soit moins formel. Par contre, as-tu une source pour les machines symétriques ? --Fschwarzentruber (discuter) 7 janvier 2016 à 19:50 (CET)
Exemple
modifierJ'ai rajouté un exemple. Il faut rajouter des exemples après (tous les problèmes SL-complets peuvent aller dans la liste en bas) ː)--Fschwarzentruber (discuter) 7 janvier 2016 à 19:48 (CET)
J'ai rajouté l'exemple du langage MULT. Je ne suis pas satisfait par l'explication de l'algorithme. Un schéma comparant l'algorithme au fait de poser une multiplication permettrais de faciliter l'explication. --Jean Jouve (discuter) 5 novembre 2018 à 13:50 (CET)