Maths pures, physique, logique (braingames.ru) : jeux cérébraux non liés au commerce - page 73

 
(1) Si une réponse positive à une question peut être vérifiée rapidement (en temps polynomial) (à l'aide d'une information auxiliaire appelée certificat), est-il vrai que la réponse elle-même (avec le certificat) à cette question peut également être trouvée rapidement?
 
aharata:

(1) Si une réponse positive à une question peut être rapidement (en temps polynomial) vérifiée (à l'aide d'une information auxiliaire appelée certificat), est-il vrai que la réponse elle-même (avec le certificat) à cette question peut également être rapidement trouvée ?
Non, le contre-exemple le plus simple et le plus connu est la multiplication d'un grand nombre par le produit de deux nombres premiers.
 
alsu:
Non, le contre-exemple le plus simple et le plus connu est la multiplication d'un grand nombre étant le produit de deux nombres premiers.
Bien que, bien sûr, il existe un algorithme de Shor quantique, donc dans le contexte de ce problème, cet exemple pourrait ne pas fonctionner
 
Cela semble être l'un des problèmes non résolus des mathématiques. Ou je suis confus à propos de quelque chose.
 
Mathemat:
Cela semble être l'un des problèmes non résolus des mathématiques. Ou peut-être que je me suis trompé.
Chut... quelqu'un va le résoudre, et on aura un million de livres... :-)
 
aharata:
Chut... quelqu'un va décider, et alors nous prendrons le million de livres... :-)
Le mathématicien américain George Danzig, alors qu'il était étudiant à l'université, est arrivé un jour en retard à son cours et a pris les équations écrites au tableau pour ses devoirs. La tâche semblait plus difficile que d'habitude, mais quelques jours plus tard, il a pu la terminer. Il s'est avéré qu'il avait résolu deux problèmes "insolubles" de statistiques auxquels de nombreux scientifiques étaient confrontés. =)
 
aharata:
Chut... quelqu'un va décider, et alors on prendra le million de livres... :-)
Qu'y a-t-il à résoudre, difficulté 1, faisons-le maintenant))
 

J'ai surtout été satisfait de ce problème (les classes sont P et NP).

Aujourd'hui, la plupart des mathématiciens pensent que ces classes ne sont pas égales. Selon une enquête menée en 2002 auprès de 100 scientifiques, 61 pensent que la réponse est "non égale", 9 pensent qu'elle est "égale", 22 trouvent qu'il est difficile de répondre et 8 pensent que l'hypothèse n'est pas déductible du système actuel d'axiomes et ne peut donc pas être prouvée ou réfutée.
 
Mathemat:

(4) Brainiac a la forme d'un triangle rectangle. La frontière intérieure le divise en deux états de superficie égale. Décrivez la forme et l'emplacement de la frontière si l'on sait qu'elle est continue et de la plus courte longueur possible.

De toute évidence, quelle que soit la division, au moins une des parties est un coin du triangle original coupé du reste par une courbe (ou une ligne droite). C'est un peu fastidieux, mais assez facile de montrer que la longueur la plus courte tout en gardant l'aire 1/2 sera le segment qui divise 2 côtés du triangle dans le rapport 1:sqrt(2) chacun (c'est-à-dire en coupant le plus petit triangle équilatéral de l'original).
 
alsu:
De toute évidence, quelle que soit la division, au moins une des parties est un coin du triangle original coupé par une courbe (ou une ligne droite) du reste du triangle. C'est un peu fastidieux, mais assez facile de montrer que la longueur la plus courte tout en gardant l'aire 1/2 sera le segment qui divise 2 côtés du triangle dans le rapport 1:sqrt(2) chacun (c'est-à-dire en coupant le plus petit triangle équilatéral de l'original).
IMHO ce ne sera pas une ligne droite =) et vous pouvez le prouver sans être fastidieux du tout.