hallavar

Posté le 03/09/2022 à 00:24:24

Ok ok, je vois le truc pour décidabilité..

Enfin là pour P = NP, je ne vois pas trop le rapport.

Si on veut montrer que P = NP, bon bah on trouve une résolution polynomiale à un algorithme NP-complet.
Si on veut prouver que P =/= NP on trouve un algorithme NP dont la complexité admet une borne inférieure non polynomiale.

Genre, je ne vois pas vraiment comment ca pourrait être indécidable du coup...

CongolaisDeterr

Posté le 03/09/2022 à 00:29:57

Citation de hallavar
Ok ok, je vois le truc pour décidabilité..
Enfin là pour P = NP, je ne vois pas trop le rapport.
Si on veut montrer que P = NP, bon bah on trouve une résolution polynomiale à un algorithme NP-complet.
Si on veut prouver que P =/= NP on trouve un algorithme NP dont la complexité admet une borne inférieure non polynomiale.
Genre, je ne vois pas vraiment comment ca pourrait être indécidable du coup...

P = NP c'est genre pour tout NP il y a P par seulement une fois

hallavar

Posté le 03/09/2022 à 00:34:15

Citation de CongolaisDeterr
P = NP c'est genre pour tout NP il y a P par seulement une fois

Oui mais tous les NP peuvent se ramener à des algo de type NP complet. Donc si tu le montre pour un NP-complet, tu as gagné..

Mais en fait sur cette question de indécidable, ca dépend de l'arithmétique que tu choisis je crois. Et là je suis trop low IQ pour t'en parlé..

hallavar

Posté le 03/09/2022 à 00:39:27

Ouai mais non, si j'ai compris en fait : j'ai dis de la merde.

Modo suppr

CongolaisDeterr

Posté le 03/09/2022 à 00:41:08

Citation de hallavar
Oui mais tous les NP peuvent se ramener à des algo de type NP complet. Donc si tu le montre pour un NP-complet, tu as gagné..
Mais en fait sur cette question de indécidable, ca dépend de l'arithmétique que tu choisis je crois. Et là je suis trop low IQ pour t'en parlé..

merci de preciser en vrai je sous entendais ca pour moi c'est pareil j'ai pas compris la difference c'est pas juste qu'il est plus dur ? l'indécidablilité de ce que j'ai compris c'est juste que l'on ne pourra jamais demontrer que c'est vrai ou faux c'est tout (dans les axiomes utilisés)

CongolaisDeterr

Posté le 03/09/2022 à 00:51:55

Oui, j'ai un level 0 en math mais de ce que j'avais lu avec le theoreme d'incompletude/completude de Godel c'est la seule facon de "rendre" une equation decidable

Sekiin 🌈

Posté le 03/09/2022 à 00:53:06

On a découvert les mathématiques, on ne les a pas inventé

hallavar

Posté le 03/09/2022 à 00:55:48

Purée et c'est pas comme si il y avait un paragraphe wikipédia sur l'indécidabilité. Et que ce paragraphe etait plutot très clair et explicite en plus.
Je suis completement con.

https://fr.m.wikipedia.or[...]e_P_%E2%89%9F_NP_dans_ZFC

CongolaisDeterr

Posté le 03/09/2022 à 01:00:29

Oui bon explicite faut pas abuser

CongolaisDeterr

Posté le 03/09/2022 à 01:18:03

hallavar

Posté le 03/09/2022 à 01:20:29

Citation de CongolaisDeterr
Donc einstein a inventer la relativité générale ?

Oui.
Il a vu que des observations ne convenaient pas à la relativité restreinte, il a donc établi la relativité générale.

Une théorie c'est un modèle d'explication, le monde reel n'est pas un modèle.
On essaie d'établir la théorie la plus proche du monde reel.

On adapte toujours la théorie aux observations, pas les observations à la théorie

CongolaisDeterr

Posté le 03/09/2022 à 01:26:57

J'ai rien compris, mais j'ai pris un mauvais exemple meme si la physique est proche ca reste plutot different des maths.
Vous avez pas une theorie connu en math pour que je puisses comprendre ?