Diskussion:Erfüllbarkeitsproblem für quantifizierte boolesche Formeln

Lemma: Erfüllbarkeitsproblem für quantifizierte boolesche Formeln

Ich kann mich mit dem Lemma noch nicht so ganz anfreunden... sollte es nicht eher Quantifiziertes Erfüllbarkeitsproblem für boolesche Formeln oder Wahrheitsproblem für quantifizierte boolesche Formeln heißen?--Grüße, Spid 14:53, 7. Apr. 2007 (CEST)

Ach was, Meinung geändert, das Lemma ist OK--Spid 18:31, 7. Apr. 2007 (CEST)

Lösungsalgorithmus QBF

In der derzeitigen Formulierung (ersetze für jeden Quantor die Formel durch zwei Formeln für x=0 und x=1) hat meiner Meinung nach die Formel auf der untersten Quantorenebene Länge exponentiell in der Anzahl der Quantoren. Der Algorithmus löst das Problem natürlich, die Zugehörigkeit zu PSPACE ist so allerdings nicht zu zeigen. Meine Studenten sind bei der Recherche zu dieser Aufgabe reihenweise in diese Falle getappt. Hier sollte besser der rekursive Algorithmus der englischsprachigen Wikipedia verwendet werden, der mit linearem Speicherplatzverbrauch auskommt. (nicht signierter Beitrag von 141.2.20.2 (Diskussion) 15:00, 5. Jul 2011 (CEST))

Fehlende Allgemeinverständlichkeit

In Sachen "Fehlender Allgemeinverständlichkeit" hat der Artikel gute Aussichten einen Platz unter den TopTen bei WP einzunehmen. Selbst bei der Einleitung kann man nicht einmal mehr "Bahnhof verstehen". {{Allgemeinverständlichkeit}}-Baustein gesetzt.--Ciao • Bestoernesto • ✉ 22:40, 12. Mai 2019 (CEST)

Toll, um das mal konstruktiv vorzutreiben also: Nur warum? --Complex (Diskussion) 23:01, 12. Mai 2019 (CEST)

@Bestoernesto: --Complex (Diskussion) 00:42, 14. Mai 2019 (CEST)

Warum? Das frägst Du noch? Wahrscheinlich bist Du Mathematiker, aber bei Weitem haben nicht alle WP-Leser studiert, geschweige denn Mathematik. Der Artikel, entspricht nicht mal ansatzweise den Allgemeinverständlichkeitsvorgaben--Ciao • Bestoernesto • ✉ 18:38, 15. Mai 2019 (CEST)

Warum frage ich weiterhin. Und warte auf eine Antwort auf meine Frage. Tagelang. Und du lieferst nicht und revertierst einen Baustein wieder rein, der noch nicht mal sachgerecht plaziert wurde. Nu ja. Dann fangen wir also von vorne an: "um das mal konstruktiv vorzutreiben also: Nur warum"?. --Complex (Diskussion) 23:51, 15. Mai 2019 (CEST)

Ach du Armer, tut mir schrecklich leid, dass du drei Tage auf eine Antwort warten musstest. Ich bitte um Vergebung. Aber dir zum Troste, es gibt abertausende Fragen auf WP-Diskseiten, die schon jahrelang unbeantwortet geblieben sind. Sollte allerdings eine WP-Richtlinie über eine Fristenregelung zur Beantwortung von Fragen auf Disk-Seiten sich meiner bisherigen Kenntnisnahme entzogen haben, bitte ich hier um Aufklärung mit Verlinkung.

Und verdrehe hier bitte keine Tatsachen. Ich habe den Baustein gesetzt und nochmal gesetzt und du revertierst ihn jedes mal wieder raus.

Und meine Antwort hast du oben klar und unmissverständlich erhalten, inklusive Link zur entsprechenden WP-Richtlinie. Hier zum dritten und letzten Mal: [ Wikipedia:Allgemeinverständlichkeit ] (diesmal in eckigen Klammern für den Fall das du an Tritanopie oder Achromatopsie leidest und meine zwei bisherigen Wikilinks gar nicht wahrnehmen konntest). Dort solltest du dich mal hin bequemen und die Beantwortung deines "warum" nachlesen. Insbesondere den ersten, aber auch den zweiten und dritten Abschnitt, obwohl eigentlich die Einleitung der WP-Richtlinie dort schon das Wesentliche aussagt. Dort findest du übrigens auch einen Hinweis über den vorgesehenen Ort der Platzierung des Bausteins entsprechend meiner Setzung. Dass ich dir die WP-Richtlinie auch noch hier her kopiere erwartest du ja wohl nicht, oder?--Ciao • Bestoernesto • ✉ 05:20, 17. Mai 2019 (CEST)

Und noch immer steht der Artikel nicht auf Wikipedia:Unverständliche Artikel und noch immer finde ich zwar agressiven Ton, aber nicht konkret, was genau denn unverständlich sein soll. --Complex (Diskussion) 14:20, 17. Mai 2019 (CEST)

Vielleicht hilft eine dritte Äußerung (ich bin vom Fach): Der Artikel ist allgemeinverständlich, erfüllt aber nicht jeden einzelnen Punkt von WP:Allgemeinverständlichkeit#Checkliste – Wikilinks wie auf Quantor und Aussagenlogik fehlen.

Es ist gut auf Mängel hinzuweisen, aber ein einzelner Baustein ohne konkrete Begründung ist zu unkonkret. Auch ansonsten halte ich hier den Baustein für die falsche Aktion. Die Wikilinks kann ich jetzt aber wegen Seitenschutz nicht einbauen, vielen Dank für die Aktion von euch beiden! --Bejahend (Diskussion) 15:17, 17. Mai 2019 (CEST)

PS: „einen Platz unter den TopTen bei WP“ – gehts noch? Schau dir mal z. B. Complex Event Processing an. --Bejahend (Diskussion) 15:21, 17. Mai 2019 (CEST)

Quantoren zu verlinken ist in der Tat sinnvoll, bei Aussagenlogik bin ich etwas unschlüssig, Erfüllbarkeitsproblem der Aussagenlogik finde ich da eigentlich zieltreffender für jemanden der über dieses Lemma stolpert. --Complex (Diskussion) 15:50, 17. Mai 2019 (CEST)

Warum nicht beides?

In der Komplexitätstheorie ist das Erfüllbarkeitsproblem für quantifizierte boolesche Formeln (oft nur kurz QBF oder QSAT) eine Verallgemeinerung des Erfüllbarkeitsproblems der Aussagenlogik. Es untersucht, ob eine mit Quantoren versehene aussagenlogische Formel erfüllbar oder wahr ist. Es ist das kanonische PSPACE-vollständige Problem.

Weiter unten im Artikel kann man dann noch z. B. Normalform, formale Semantik verlinken. Ich bin mir allerdings nicht ganz sicher, ob die zusätzlichen Links einen ohnehin schon allgemeinverständlichen Text noch allgemeinverständlicher machen, aber die Verlinkung kann guter Service sein, wenn man mal etwas genauer nachlesen möchte... --Bejahend (Diskussion) 16:20, 17. Mai 2019 (CEST)

Jepp, ganz auf Deiner Linie. @Bestoernesto: wäre das befriedigend, sodass der Seitenschutz aufgehoben werden kann? --Complex (Diskussion) 15:50, 18. Mai 2019 (CEST)

Complex, dein argumentum ad hominem mir hier Aggressionen vor zu werfen und dein rhetorischer Trick den diskussionsfernen Aspekt des fehlenden Abschnitts auf der Projektseite "Unverständliche Artikel" einzubringen ist nicht zielführend. Davon abgesehen kann man, so man will, auf dem Baustein selbst, bei Vorlage:Allgemeinverständlichkeit und drittens bei der besagten Projektseite selbst, deutlich lesen, dass dort die Abschnitte zur Eintragung der betroffenen Artikel automatisch erstellt werden. Das GiftBot das (noch) nicht erledigt hat, hat nicht mein Problem zu sein.

Bejahend, dein freundliches Bemühen hier eine Lösung herbei zu führen ist gut gemeint, aber nur bedingt hilfreich, da Du, wie Du ja selbst schreibst, "vom Fach" bist. So ist es nicht verwunderlich, dass Du den Artikel als allgemeinverständlich empfindest. Dass das ein* Heizungsinstallateur*n, eine Krankenschwester, ein*e Mechatroniker*in, eine Bürokaffrau usw auch so sieht, wage ich sehr zu bezweifeln. Und trotz deiner kleinen vorgeschlagenen Änderungen verstehe auch ich noch nicht wesentlich mehr.

In der Hoffnung auch die Meinung von Nichtmathematiker*innen zu erfahren, werde ich das jetzt mal auf 3M anfragen.--Ciao • Bestoernesto • ✉ 07:22, 28. Mai 2019 (CEST)

Einschub: Der Artikel behandelt ein Problem der Informatik, nicht der Mathematik, wie unschwer zu erkennen ist „Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik ....“ --Bejahend (Diskussion) 12:31, 28. Mai 2019 (CEST)

3M Ich muss beiden Seiten recht geben. Ich verstehe auch nur Bahnhof (im besten Falle) - andererseits lebt die Mathematik von praezise definierten Termina … und der scheinbare Kauderwelsch ist insoweit dem Leser (incl. meinerseits) anzulasten und nicht der Mathematik.

Quantoren sollte verlinkt werden …. und ein simpler Satz als Einleitung in Normalsprache waere wuenschenswert…. dass dann der Rest der Allgemeinheit unzugaennglich bleibt …. das laesst sich wohl gar nicht vermeiden. --DAsia (Diskussion) 10:35, 28. Mai 2019 (CEST)

3M Obwohl ich Mathe-LK bis zum Abi hatte, und meine, ein klein wenig Orientierung zu haben, bin ich in vielen Mathematik-Artikeln in Wikipedia in kürzester Zeit am Ende des Verständnisses. Das wünsche ich mir oft anders, aber habe auch eine Ahnung, dass das kaum umzusetzen ist, da die Materie wirklich komplex ist und jeder benutzte Begriff schon ein Verständnis voraussetzt, das man einfach haben muss. Konkret zu diesem Artikel: Den ersten Absatz finde ich grammatikalisch schön schlicht gehalten, da sehe ich keine unnötige Verkomplizierung des Sachverhaltes. Der zweite Absatz wirkt sehr komprimiert; vielleicht kann das etwas flächiger ausgeführt werden mit der Chance auf mehr Verständlichkeit. Es sollten in den Absätzen, soweit sinnvoll möglich, die Begriffe "Quantoren", "kanonisch", "boolsche Formel", "(freie) Variable", "Erfüllbarkeit", "äquivalent" und "Wahrheit" verlinkt sein. Das gibt dem Leser zusätzliche Chance, sich zu einem Verständnis in die Materie reinzuarbeiten. Grüße, --Coyote III (Diskussion) 11:18, 28. Mai 2019 (CEST)

> erg.: ein Wartungsbaustein bedarf - spätestens auf Nachfrage - einer wirklichen Erläuterung. --Coyote III (Diskussion) 11:24, 28. Mai 2019 (CEST)

@Coyote III: „Kanonisch“ ist hier eigentlich kein Fachbegriff, sondern steht für Bedeutung 1 in [1]. Vielleicht könnte man es für einfachere Sprache etwas umformulieren: „Es ist das klassische Beispiel eines PSPACE-vollständigen Problems.“ --Bejahend (Diskussion) 11:37, 29. Mai 2019 (CEST)

Nachtrag: Ich habe die Wikilinks nun ergänzt. Kanonisch ist jetzt erläutert. „Boolsche Formel“ zu verlinken ist nicht sinnvoll (das Lemma heißt „quantifizierte boolesche Formel“, Zirkellink nicht sinnvoll). Meines Erachtens gibt es auch keine „boolsche Formel“, das wäre eine Begriffsbildung. „Aussagenlogische Formel“ ist verlinkt, „boolesche Algebra“ wird im Artikel leider nicht erwähnt. --Bejahend (Diskussion) 10:12, 1. Jun. 2019 (CEST)