Größe von Schaltkreisen
-
Hallo,
wenn ich eine Boolesche Formel f in konjunktiver Normalform habe, wie groß ist der kleinste Schaltkreis, der f Berechnet?
Ist das O(n*m)?
Wenn n die Anzahl der Variablen in f und m die Anzahl der Klauseln in f ist?
-
Was meinst du mit Schaltkreis? Die Anzahl der elektrischen Bauteile? Oder der Logischenverknüpfungen.
Über ersteres kann man keine Aussage machen und über 2. naja das kann man zählen aber meistens gibt es noch einen einfacheren Weg.
-
Ich suche eigentlich einen Beweis, dass das Inäquivalenzproblem von Schaltkreisen NP-vollständig ist.
Ich dachte mir man kann SAT folgendermaßen polynomiell reduzieren.
F Eingabe für SAT
Konstruiere in polynomieller Zeit Schaltkreis S, der F berechnet.
Schaltkreis S0 berechne für alle Eingaben immer die 0.
Teste S und S0 auf Inäquivalenz
Jetzt habe ich diesem Beweis das Problem, wie ich "in polynomieller Zeit berechenbare Funktion", auf die Konstruktion von Schaltkreisen anwende.