Reine Mathematik, Physik, Logik (braingames.ru): nicht handelsbezogene Denkspiele - Seite 73

 
(1) Wenn eine positive Antwort auf eine Frage schnell (in polynomialer Zeit) verifiziert werden kann (unter Verwendung einer Hilfsinformation, die Zertifikat genannt wird), ist es dann wahr, dass die Antwort selbst (zusammen mit dem Zertifikat) auf diese Frage ebenfalls schnell gefunden werden kann?
 
aharata:

(1) Wenn eine positive Antwort auf eine Frage schnell (in polynomialer Zeit) überprüft werden kann (unter Verwendung einer Hilfsinformation, die Zertifikat genannt wird), ist es dann wahr, dass die Antwort selbst (zusammen mit dem Zertifikat) auf diese Frage ebenfalls schnell gefunden werden kann?
Nein, das einfachste und weithin bekannte Gegenbeispiel ist die Multiplikation einer großen Zahl mit dem Produkt zweier Primzahlen
 
alsu:
Nein, das einfachste und weithin bekannte Gegenbeispiel ist die Multiplikation einer großen Zahl mit dem Produkt zweier Primzahlen.
Allerdings gibt es natürlich einen Quanten-Shor-Algorithmus, so dass dieses Beispiel im Zusammenhang mit diesem Problem möglicherweise nicht funktioniert
 
Dies scheint eines der ungelösten Probleme der Mathematik zu sein. Oder habe ich etwas falsch verstanden?
 
Mathemat:
Dies scheint eines der ungelösten Probleme der Mathematik zu sein. Oder vielleicht habe ich es falsch verstanden.
Jemand wird es lösen, und dann bekommen wir eine Million Pfund... :-)
 
aharata:
Pst... jemand wird entscheiden, und dann nehmen wir die Million Pfund... :-)
Der amerikanische Mathematiker George Danzig kam als Universitätsstudent einmal zu spät zum Unterricht und verwechselte die an die Tafel geschriebenen Gleichungen mit seinen Hausaufgaben. Es schien schwieriger zu sein als sonst, aber ein paar Tage später war er in der Lage, es zu beenden. Es stellte sich heraus, dass er zwei "unlösbare" Probleme in der Statistik gelöst hatte, mit denen viele Wissenschaftler zu kämpfen hatten. =)
 
aharata:
Pst... jemand wird entscheiden, und dann nehmen wir die Million Pfund... :-)
Was gibt es da zu lösen, Schwierigkeit 1, los geht's))
 

Am meisten hat mir dieses Problem gefallen (die Klassen sind P und NP).

Heutzutage glauben die meisten Mathematiker, dass diese Klassen nicht gleich sind. Dies ergab eine 2002 durchgeführte Umfrage unter 100 Wissenschaftlern, 61 sind der Meinung, dass die Antwort "nicht gleich" ist, 9 sind der Meinung, dass sie "gleich" ist, 22 finden es schwierig zu beantworten und 8 sind der Meinung, dass die Hypothese nicht aus dem derzeitigen Axiomensystem ableitbar ist und somit weder bewiesen noch widerlegt werden kann.
 
Mathemat:

(4) Brainiac hat die Form eines rechtwinkligen Dreiecks. Die innere Grenze teilt es in zwei Staaten gleicher Fläche. Beschreiben Sie die Form und die Lage der Grenze, wenn bekannt ist, dass sie durchgängig und von möglichst geringer Länge ist.

Unabhängig von der Teilung ist natürlich mindestens ein Teil eine Ecke des ursprünglichen Dreiecks, die durch eine Kurve (oder eine gerade Linie) vom Rest abgeschnitten ist. Es ist etwas mühsam, aber einfach genug zu zeigen, dass die kürzeste Länge unter Beibehaltung des Flächeninhalts 1/2 das Segment ist, das zwei Seiten des Dreiecks im Verhältnis 1:sqrt(2) teilt (d. h. das kleinere gleichseitige Dreieck vom ursprünglichen abschneidet).
 
alsu:
Unabhängig von der Teilung ist mindestens einer der Teile eine Ecke des ursprünglichen Dreiecks, die durch eine Kurve (oder gerade Linie) vom Rest des Dreiecks abgeschnitten ist. Es ist etwas mühsam, aber einfach genug zu zeigen, dass die kürzeste Länge unter Beibehaltung des Flächeninhalts 1/2 das Segment ist, das zwei Seiten des Dreiecks im Verhältnis 1:sqrt(2) teilt (d. h. das kleinere gleichseitige Dreieck vom ursprünglichen abschneidet).
IMHO wird es dort keine gerade Linie sein =) und Sie können es beweisen, ohne langwierig zu sein