Discussion :

[Unnamed_]

Bonsoir à tous
voilà, ça fait genre un an que je me frotte à P=NP (ce mec est malade pensez vous probablement).
J'ai commencé par attaquer le TSP sans succès, puis le sac à dos, le problème des sous-ensembles.
et depuis presque un mois j'ai commencé à travailler sur le problème de coloration de graphe, et je pense avoir trouvé un algorithme qui puisse déterminer si un graphe peut être coloré en k couleurs en temps polynomial.
Je vous fait un topo, la complexité de l'algo dépend de k (le nombre des couleurs) et pour k fixé, l'ago est purement polynomial en fonction du nombre des sommets.
Jusque là ça a l'air de fonctionner, et j'aimerai bien publier un article dessus, sauf que je ne sais pas ce que mes travaux valent.
Je me remets à vous car aucun des prof que j'ai consulté n'a voulu me prendre au sérieux, je suis étudiant en première année prépa
PS : Désolé, je ne peux malheureusement pas détailler la méthode, ni l'algo.

[kwariz]

Bonjour,

ce genre de titre est toujours un peu racoleur

Si tu penses avoir un algorithme répondant correctement au problème de décision «le graphe G est-il k-coloriable» quels que soient le graphe G et k>2 qui est dans FPT, c'est-à-dire dont la complexité est en f(k).V^O(1), avec f quelconque et V le nombre de sommets du graphe G, alors oui dans ce cas P=NP.
Tu peux le publier où tu veux ... mais il faudra le montrer tôt ou tard. Si tu ne le montres pas on ne pourra ni te féliciter, ni te montrer où est ton erreur (pour autant que tu sois sérieux, que ton texte soit lisible, etc.).

Essaye aussi en utilisant la réduction classique du k-coloriage vers SAT, juste pour voir ...

[Unnamed_]

La réduction n'est pas trop du domaine de mes compétences, remarque, j'ai tout appris en autodidacte (c'est difficile à la longue).
Sinon la forme générale est de f(k)g(k, V). avec g(k, V) != V^O(1) (une éventuelle optimisation de l'algorithme peut palier ce manque)
Quand on fixe k on tombe sur un cas particulier.
Par exemple pour k=3 la complexité est un O(n^4)
En gros, si on fixe k, on tombe toujours sur un cas particulier.
la complexité pour k=3 est différente de celle pour k=4 ...

[kwariz]

Tu n'arrives pas à avoir une complexité «séparée» en deux avec d'un côté une expression qui dépend de k mais pas du tout de V, et de l'autre une expression qui dépend de V et pas du tout de k ?

[Unnamed_]

Oui voilà, c'est d'ailleurs pour cette raison en particulier que je n'arrive pas à savoir si mes travaux valent réellement quelque chose.
sinon, je peux y arriver, mais seulement pour V borné.
D'ailleurs, il y'a quelques mois j'ai aussi élaboré un algorithme polynomiale ne dépendant que de n cette fois et qui résout le TSP, le sac à dos, les sous-ensembles ... mais seulement pour les petites instances de n.

[kwariz]

Dit comme ça ça ne prouve pas grand chose ... c'est comme dire qu'il existe un algorithme en temps constant pour trier un tableau de taille n avec n borné, ce qui n'est pas faux. On peut considérer un algorithme qui trie un tableau de 3 éléments comme en temps constant, mais cela n'apporte rien au problème général du tri de tableau de taille n quelconque.

[Unnamed_]

oui, je vois
sinon dans le cas de la deuxième fonction g dont dépend la complexité et qui elle même dépend de k et V.
Si je n'arrive pas à séparer V de k, ça ne vaut toujours rien ?
On ne peut pas traiter le problème comme un cas particulier, comme celui du 2-coloriage ou 2-SAT, genre exclure le 3-coloriage de NP ?

[kwariz]

Heu je ne comprends pas ta question ... 2SAT est dans P, tout comme le 2-coloriage ....
Si on prend ton algo, quelle en est la complexité en fonction de k,V et E (avec V le nombre de sommets, E le nombre d'arrêtes) ?

[Unnamed_]

la complexité de l'algo en général est k².V^O(k)
J'ai choisi un mauvais exemple pour le 2-SAT
disons exclure le 3-coloriage de NP comme pour le problème d'affectation avec l'algorithme hongrois

[kwariz]

k²V^O(k) ce n'est pas suffisant. Il faut que l'exposant de V soit totalement indépendant de ton paramètre k, il doit être borné par une constante.

[Unnamed_]

Noté
merci de m'avoir éclairé

[souviron34]

je pense avoir trouvé un algorithme qui puisse déterminer si un graphe peut être coloré en k couleurs en temps polynomial.
Je vous fait un topo, la complexité de l'algo dépend de k (le nombre des couleurs) et pour k fixé, l'ago est purement polynomial en fonction du nombre des sommets.

C'est à dire ??

O (Nk) ??