Ein direkter Produktsatz besagt informell, dass das Berechnen von Instanzen einer Funktion f schwieriger ist als das einmalige Berechnen von f .
Typische direkte Produktsätze (z. B. Yaos XOR-Lemma) betrachten die Komplexität im Durchschnitt und argumentieren (sehr grob), dass nicht durch Schaltungen der Größe mit einer Wahrscheinlichkeit besser als p berechnet werden kann , dann können Kopien von nicht durch berechnet werden Schaltungen der Größe mit einer Wahrscheinlichkeit besser als .
Ich suche nach verschiedenen Arten direkter Produktsätze (sofern bekannt). Speziell:
(1) Nehmen wir an, wir legen die Fehlerwahrscheinlichkeit und interessieren uns stattdessen für die Größe der Schaltung, die zur Berechnung von Kopien von . Gibt es ein Ergebnis, das besagt, dass wenn nicht durch Schaltungen der Größe mit einer Wahrscheinlichkeit besser als berechnet werden kann , Kopien von nicht mit einer Wahrscheinlichkeit besser als Verwendung einer Schaltung der Größe kleiner als berechnet werden können ?
(2) Was ist in Bezug auf die Komplexität im schlimmsten Fall bekannt ? Wenn nicht durch Schaltungen der Größe (mit 0 Fehlern) berechnet werden kann , was können wir über die Komplexität der Berechnung von Kopien von (mit 0 Fehlern) sagen ?
Alle Referenzen wäre dankbar.
Um die Antwort von Or zu ergänzen, wurden Fragen zum Geschmack von (1) [wie viel einer Ressource benötigt wird, um auf k Kopien gut abzuschneiden] untersucht, und die entsprechenden Theoreme werden "direkte Summensätze" genannt. Wie bei direkten Produktsätzen können direkte Summensätze je nach Aufbau gelten oder auch nicht.
quelle