Discussion:Sharp-P

Classe de fonctions ou caractérisation de problèmes?

Les deux premières phrases sont contradictoires: « Contrairement à la plupart des autres classes de complexité, ce n'est pas une classe de problèmes de décision mais une classe de fonctions calculables. Il s'agit de compter le nombre de solutions du problème ». Il me semble que cela dit clairement que ça caractérise les problèmes et pas les fonctions. --Pierre de Lyon (discuter) 12 juin 2014 à 22:08 (CEST)

La version anglaise dit qu'il s'agit d'une classe de « problèmes associés à une fonction » et non pas de d'une classe de « problèmes associés à une décision ». Donc il s'agit bien d'une classe de problèmes. --Pierre de Lyon (discuter) 12 juin 2014 à 22:17 (CEST)

Bonjour, je ne sais pas quelle est la bonne façon de tourner la phrase d'introduction, et je te laisse modifier comme tu l'entends, mais pour ce qui est de la définition formelle, je suis sûr de moi (je vais rajouter une autre référence en passant). --Roll-Morton (discuter) 13 juin 2014 à 11:30 (CEST)

Si tu es sûr de toi pour la définition formelle, tu assumes donc l'incohérence avec la définition dans le wikipédia anglais et le wikipédia allemand. C'est amusant! Je ne suis pas un spécialiste de #-P, et j'aurais dû demandé sa définition à Valiant quand j'ai eu l'occasion de discuter avec lui. Je persiste néanmoins à penser que la classe #-P est une classe de problèmes et pas une classe de fonctions. --Pierre de Lyon (discuter) 13 juin 2014 à 11:44 (CEST)

Je vais être plus précis. Prenons la définition du Wikipédia anglais: "More formally, #P is the class of function problems of the form "compute ƒ(x)", where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time". Elle dit que #P est la classe des « function problems » donc elle dit que #P est une classe de problèmes qui demandent de calculer une fonction, ce que j'ai appelé une classe de « problèmes associés à une fonction ». Je me demande s'il n'y a pas eu une erreur de traduction en traduisant « function problem » par « fonction ». En allemand c'est plus direct : « Ein Problem ist in der Klasse #P, wenn eine nichtdeterministische Turingmaschine existiert ... » qui veut dire: « Un problème est dans la classe #P s'il existe une machine de Turing non déterministe ... »--Pierre de Lyon (discuter) 13 juin 2014 à 12:05 (CEST)

Mmm, je pense qu'on peut avoir les deux points de vue : un ensemble de fonctions ou un ensemble de problème "calculer la fonction". Il me semble que ça n'est qu'une question de formalisme. Je ne suis pas spécialiste non plus, j'ai juste plusieurs références auxquelles je fais confiance : le Arork/Barak et le Perifel (le second s'inspirant du premier) qui définissent #P comme un ensemble de fonctions. Cependant ils parlent ensuite des "problèmes de la classe", en faisant il me semble la bijection entre f et calculer f.--Roll-Morton (discuter) 13 juin 2014 à 14:06 (CEST)

Ce n'est pas très important à la fin. Le définition originale est dans The complexity of computing the permanent de Valiant. La définition est donnée pour un problème en introduction, pour une fonction dans la partie formelle. Zandr4^[Kupopo ?] 13 juin 2014 à 15:20 (CEST)

J'ai reformulé le début de l'article. J'ai rajouté une image d'un arbre de calcul. J'ai mis un tableau dans la section "Exemples de problèmes" (anciennement "Présentation"). J'espère que vous aimez. --Fschwarzentruber (discuter) 6 juin 2016 à 01:16 (CEST)

 Zandr4 : Je vous trouve un peu léger de dire que ce n'est pas très important de savoir si c'est la définition d'un problème ou celle d'une fonction. Je n'en écris pas plus car je risquerais de ne pas être gentil. Je constate que j'ai posé la question il y a deux ans et qu'elle n'est toujours pas résolue ou plutôt si, comme l'article commence par une contradiction, tout ce qui s'ensuit est un ensemble de conséquences logiques. --Pierre de Lyon (discuter) 14 juillet 2016 à 19:09 (CEST)

 PIerre.Lescanne : Vous avez bien fait de ne pas écrire plus alors :) Avez-vous résolu le problème ? Je vois toujours des passages de "fonction" à "problème" de manière assez anarchique dans l'article. Zandr4^[Kupopo ?] 24 mars 2017 à 12:37 (CET)

Après avoir lu ce que Perifel en écrit, j'ai proposé ma formulation. --Pierre de Lyon (discuter) 17 juillet 2016 à 13:23 (CEST)

Merci. Mais au lieu d'une réf, cela peut aller dans le corps du texte dans la partie "Définition formelle". Ou peut-être donner un exemple directement dans l'introduction ? Mais... lequel ? Qu'en pensez-vous ?--Fschwarzentruber (discuter) 17 juillet 2016 à 13:28 (CEST)

Mon idée c'est que tout tourne autour de la fonction de comptage et qu'il faut en parler très tôt, c'est-à-dire dans l'introduction. Le formalisme que j'utilise est modéré, mais comme c'est néanmoins du formalisme, j'ai voulu le mettre en note en bas de page, mais nous ne sommes pas obligé. --Pierre de Lyon (discuter) 18 juillet 2016 à 09:49 (CEST)

Je trouve qu'il n'y a pas besoin de formalisme. Mais ce n'est que mon avis personnel. Je propose quelque chose comme "Une fonction de comptage associe à tout entrée du problème le nombre de solutions. Par exemple, pour le comptage du nombre de 3-coloration d'un graphe, la fonction de comptage associe à tout graphe le nombre de 3-colorations possibles.". Mais on peut aussi laisser le formalisme en bas de page car c'est discret. Mais le formalisme est donné dans "Définition formelle". Mais, je ne sais pas ce qu'est sigma dans la définition proposée. --Fschwarzentruber (discuter) 18 juillet 2016 à 13:56 (CEST)

D'autres formulations équivalentes ?

Ce qui fait la force de la théorie de la décision, c'est qu'elle peut-être énoncée dans plusieurs formalismes très différents qui sont montrés équivalents. A en croire le présent article, la complexité #P, quant à elle, ne semble définie que dans le formalisme des machines de Turing. Est-ce le cas? Ou y a-t-il d'autres définitions équivalentes? --Pierre de Lyon (discuter) 14 juillet 2016 à 19:15 (CEST)

Je ne sais pas bien. Il faut farfouiller un peu plus les livres pour voir s'il existe des définitions alternatives. Mais #P demande de compter le nombre d'exécutions. Donc il faut un modèle avec du non-déterminisme. --Fschwarzentruber (discuter) 14 juillet 2016 à 23:18 (CEST)