P!=np
11 messages
- Page 1 sur 1
par bfure » 09 Nov 2010, 11:14
Pour résoudre ce problème, trouver un NP et démontrer qu'il n'appartient pas à P est-il suffisant ?
par bfure » 14 Nov 2010, 21:50
un problème dont le temps augment de manière 2 puissance n est il NP ?
par Doraki » 14 Nov 2010, 22:04
Pas nécéssairement.
La classe de complexité EXPTIME est strictement plus grande que la classe NP.
Bon EXPTIME c'est un peu plus large que "2^n" donc ptetre que ça suffit pas mais j'pense quand même a priori qu'il y a des problèmes en temps 2^n qui ne sont pas NP.
La classe de complexité EXPTIME est strictement plus grande que la classe NP.
Bon EXPTIME c'est un peu plus large que "2^n" donc ptetre que ça suffit pas mais j'pense quand même a priori qu'il y a des problèmes en temps 2^n qui ne sont pas NP.
par Patastronch » 15 Nov 2010, 09:32
En effet, il y a une infinité de classes entre NP et EXPTIME et on peut en inventer autant qu'on veut d'ailleurs. Un excellent livre sur la théorie de la complexité est le suivant : http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455
Tu es dans NP si l'optimalité d'une solution de ton problème peut se vérifier en temps polynomiale (et que la taille de ton problème peut se coder polynomialement) . En gros si tu possède un oracle capable de te fournir directement la bonne solution de ton problème et que tu es capable de la vérifier en temps polynomiale en fonction de la taille de ton problème, alors tu es dans NP.
Le problème est dit NP-difficile si ton problème peut être le résultat d'une réduction polynamiale à partir d'un problème prouvé comme étant NP-difficile (comme 3-SAT par exemple)
Enfin tu es NP-complet si ton problème est dans NP et qu'il est NP-difficile.
Il y en a un paquet meme et inversement ce n'est pas parce qu'on est dans NP qu'on est exponentiel.
Ce sont les problèmes NP-Complet qui sont difficiles à résoudre (en temps non polynomiale) dans la classe NP. Les autres peuvent se résoudre à coup de programmation dynamique ou autres méthodes d'optimisation combinatoire classique.
Tu es dans NP si l'optimalité d'une solution de ton problème peut se vérifier en temps polynomiale (et que la taille de ton problème peut se coder polynomialement) . En gros si tu possède un oracle capable de te fournir directement la bonne solution de ton problème et que tu es capable de la vérifier en temps polynomiale en fonction de la taille de ton problème, alors tu es dans NP.
Le problème est dit NP-difficile si ton problème peut être le résultat d'une réduction polynamiale à partir d'un problème prouvé comme étant NP-difficile (comme 3-SAT par exemple)
Enfin tu es NP-complet si ton problème est dans NP et qu'il est NP-difficile.
Bon EXPTIME c'est un peu plus large que "2^n" donc ptetre que ça suffit pas mais j'pense quand même a priori qu'il y a des problèmes en temps 2^n qui ne sont pas NP.
Il y en a un paquet meme et inversement ce n'est pas parce qu'on est dans NP qu'on est exponentiel.
Ce sont les problèmes NP-Complet qui sont difficiles à résoudre (en temps non polynomiale) dans la classe NP. Les autres peuvent se résoudre à coup de programmation dynamique ou autres méthodes d'optimisation combinatoire classique.
par bfure » 15 Nov 2010, 15:08
Peut-on trouver un NP dont les solutions seraient totalement aléatoires ?
par Patastronch » 15 Nov 2010, 16:54
bfure a écrit:Peut-on trouver un NP dont les solutions seraient totalement aléatoires ?
Je comprend pas trop ce que tu veux dire. Les solutions d'un problèmes sont celles qui sont candidates à la résolution du problème pour moi, par exemple dans un problème de plus court chemin dans un graphe, tous les chemins sont des solutions du problème mais seules quelques unes sont de valeur minimales (seules quelques solutions résolvent notre problème).
Un problème dont toutes les solutions seraient complètement aléatoire je ne vois pas trop ce que ca voudrait dire, puisqu'un problème induit un ensemble de solutions, et on désire en déterminer une parmi ces solutions qui répond oui à une question oui/non (ou qui optimise une fonction).
par bfure » 15 Nov 2010, 17:14
L'idée serait de trouver un problème pour lequel une hypothèse n'aurait pas plus de chance d'être une bonne solution. Par exemple donner la combinaison du loto avant son tirage ou trouver la combinaison d'un coffre fort. il est facile de démontrer que pour ce type de problème, on ne peut faire autrement que de tester les possibilités les unes après les autres et que s'il existait une possibilité (un algorithme) de trouver un raccourci, ce serait incompatible avec l'équiprobabilité des solutions initiales. Si de plus le problème est NP n'aurait on pas démontrer qu'il ne puisse être P ? et que donc NP!=P.
par Doraki » 15 Nov 2010, 23:37
Il me semble qu'on a fait à peu près ce que tu décris pour exhiber un oracle O tel que relativement à cet oracle, P < NP.
L'oracle en question n'est pas basé sur de l'aléatoire mais est construit pour que tout programme P soit incapable de pleinement l'utiliser.
Désolé j'ai pas de référence sous la main.
L'oracle en question n'est pas basé sur de l'aléatoire mais est construit pour que tout programme P soit incapable de pleinement l'utiliser.
Désolé j'ai pas de référence sous la main.
par am2004 » 22 Nov 2010, 23:44
Oui c'est un article de Baker, Gill et Solovay : http://en.wikipedia.org/wiki/Oracle_machine
Doraki a écrit:Il me semble qu'on a fait à peu près ce que tu décris pour exhiber un oracle O tel que relativement à cet oracle, P < NP.
L'oracle en question n'est pas basé sur de l'aléatoire mais est construit pour que tout programme P soit incapable de pleinement l'utiliser.
Désolé j'ai pas de référence sous la main.
11 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :