Discussion:Co-NP

Sur la définition avec certificat

Bonjour,

Je ne veux pas dire de bétise mais il me semble qu'il y a une erreur dans la définition par certificat:

"Sur un alphabet $\Sigma$, un langage $L$ est dans co-NP, si il existe un polynôme $P$ et une machine de Turing en temps polynomial $M$, tels que pour un mot $x$ de taille $n$: $x\in L\Leftrightarrow \forall u\in \Sigma ^{P(n)},M(x,u)=1$."

C'est la définition de NP ça non? Co-NP ça serait plutôt $x\not \in L\Leftrightarrow \exists u\in \Sigma ^{P(n)},M(x,u)=1$

Hum, je pense que dans la définition de NP, il y a un "il existe" : il existe une preuve courte. Ici c'est un "quelque soit". Sur le fait de faire une équivalence avec x \notin L, c'est possible aussi mais c'est plus joli comme ça je trouve. Et pour donner un vrai argument : j'ai été vérifier dans le Arora et Barak cité dans les références (une préversion gratuite est disponible en ligne).--Roll-Morton (d) 13 février 2013 à 10:51 (CET)

Oui effectivement autant pour moi j'ai trop vite lu, avec le "quelque soit" plutôt que "il existe" c'est bon! --Pparent (d) 14 février 2013 à 15:29 (CET)

ps: par contre de mon coté je m'attendrait plus à lire "M(x,u)=0" plutôt que "M(x,u)=1", ce qui revient bien sur exactement au même. Car dans ma tête la machine répond oui si le certificat permets effectivement de prouver que la réponse au problème est non. Mais bon c'est un détail.

Ouep, c'est vrai que le passage au 1 est un peu bizarre (mais licite), j'ai pris la référence tel quel, en me disant qu'il y avait peut-être une raison.--Roll-Morton (d) 14 février 2013 à 18:43 (CET)

Je me suis permis de donner une définition moins formelle. C'est dur à lire sinon. Comme dit, on ne voyait pas assez le "pour tout" visuellement. J'ai écrit en texte. Le débat sur 0 ou 1 n'est pas vraiment important. La référence est par contre toujours ok (on n'est pas obligé de copier tel quel un extrait de livre. L'important c'est l'information. Si jamais vous n'êtes pas d'accord, on peut revenir à l'ancienne version. Bonne soirée. --Fschwarzentruber (discuter) 6 janvier 2016 à 17:01 (CET)

 Fschwarzentruber : Ça me va. Je vais juste changer le gras (qui n'est pas conseillé dans le corps de l'article) par de l'italique. --Roll-Morton (discuter) 6 janvier 2016 à 19:02 (CET)

Oui, tu as raison. On met en gras quand on définit une notion et quand c'est un mot important, c'est ça ? C'est sûr que là, on veut insister sur "pour tout" mais on ne le définit pas. Merci ;)--Fschwarzentruber (discuter) 6 janvier 2016 à 19:35 (CET)

Oui la convention est en gros que l'on met en gras la première apparition du sujet dans le résumé introductif. Si il y a plusieurs noms, on les met tous en gras. --Roll-Morton (discuter) 6 janvier 2016 à 19:48 (CET)

Pour les noms de classes de complexité (NP et compagnie), certains articles utilisent le gras (peut-être l'ai-je moi-même utilisé). Même dans ces cas-là (acronyme, abréviation) il vaut mieux éviter, mais bon... --Roll-Morton (discuter) 6 janvier 2016 à 19:50 (CET)

Fusion ?

A fusionner avec co-NP ? --Roll-Morton (discuter) 16 février 2015 à 12:05 (CET)

Je pense encore que c'est la chose à faire. Un autre avis ? --Roll-Morton (discuter) 18 avril 2016 à 16:25 (CEST)

Je suis du même avis. -- ManiacParisien (discuter) 25 avril 2016 à 18:18 (CEST)

 Léna et ProgVal : ok ? --Roll-Morton (discuter) 28 avril 2016 à 10:43 (CEST)

Pourquoi pas -- ProgVal (discuter) 28 avril 2016 à 18:13 (CEST)

Je suis d'accord. Fusionnons ǃ Disons ː nous supprimons l'article "co-NP-complet" et gardons l'article "co-NP".--Fschwarzentruber (discuter) 23 mai 2016 à 17:04 (CEST)

Merci pour l'avis. Techniquement, je trouve c'est mieux de fusionner, comme ça les auteurs de l'article co-NP complet sont crédités dans co-NP-complet, ce qui est plus sympa. --Roll-Morton (discuter) 23 mai 2016 à 17:42 (CEST)

Co-NP et co-NP-complet

Bonjour,

en fait cette fusion consisterai à placer le contenu de co-NP-complet dans co-NP. J'ai prévenu sur la pdd de co-NP complet et sur la pdd du projet:informatique théorique il y a déjà un moment, et j'ai eu deux réponses positives, et une non-réponse. Le contexte technique est le suivant : co-NP est une classe de complexité, un objet mathématique. Pour chacune de ces classes, on peut définir une sorte de «variante», une version «complète». Pour la plupart des classes ces variantes n'ont pas d'articles, car elles n'existent que comme variante de la classe principale. Il y a une exception : NP-complet car (en raccourci) c'est un élément important pour le problème P=NP. Co-NP complet n'est pas spéciale, et n'a pas de raison d'avoir sa classe a priori. Il y a quelques résultats qui parlent explicitement de coNP complet, mais on peut les mettre dans coNP sans problème. J'ajoute que les anglophones ont choisi d'avoir un article en:co-NP-complete, qui n'est pas très fourni, et ne le sera sans doute pas plus à l'avenir. --Roll-Morton (discuter) 23 mai 2016 à 16:05 (CEST)

 Plutôt contre Je pense que cela rendra moins claire. Je préfère à titre personnelle de faire comme les anglophones deux articles pas très fournis mais qui permette de bien voir la différence qu'un seul article très fourni mais qui va rendre les choses plus confuse. Surtout pour des personnes qui ont peu de base en informatique théorique ou en mathématique. Bien à vous--Huguespotter (discuter) 23 mai 2016 à 17:24 (CEST)

Je comprends le point de vue, et dans la plupart des cas je préfère avoir plusieurs pages, même petites. Mais ici, co-NP-complet est réduite à un lien vers coNP et à un lien vers complet (complexité), alors je me dis que ça ne vaut pas le coup...--Roll-Morton (discuter) 26 mai 2016 à 12:22 (CEST)

Plutôt pour J'ai compté les pages liées : il y a 15 pages "co-NP" et 8 pages "co-NP-complet", donc les avis sont partagés dans les autres langues aussi. La page anglaise est plus fouillée que la page française actuelle, la page allemande réserve un paragraphe à la complétude. -- ManiacParisien (discuter) 24 mai 2016 à 11:55 (CEST)