Nehmen wir an, Sie haben n boolesche Eingänge von x1, x2, x3, ..., xn. Wie stellen Sie fest, dass < = k Ihrer booleschen Eingänge True ist und nur logische ODER-Gatter verwendet, und zwar in polynomieller Zeit?Polynomial-Zeit-Logik-Puzzle mit AND/OR/NOT zu erstellen <= auf N-Eingänge?
Ich bin ganz ehrlich benommen.
Es gibt viele Möglichkeiten, dies zu tun. Eine besteht darin, (rekursiv) stellen zwei Netze:
Schließen Sie sie als (B And Not x [n]) oder ein
Können Sie ein bisschen mehr ausarbeiten? –
Was möchten Sie wissen? Ich denke, dass meine Antwort die vollständige Beschreibung des Netzwerks enthält. – user31264
Stellen Sie sich vor, dass "B" und "xn" beide wahr sind. In diesem Fall wären'k + 1'-Eingaben wahr und der Ausdruck sollte falsch sein. Der korrekte Ausdruck sollte '(B und nicht xn) oder (A und xn)' sein. Diese Lösung sieht jedoch eher exponentiell als polynomisch aus. –
Eine gute Übersicht über Mächtigkeit Ausdrücke Zähler verschiedener Art wurde gegeben durch [Carsten Sinz] (http: //www.carstensinz. de/Vorträge/CP-2005-Vortrag.pdf). –