Sie müssen vorsichtig sein, wenn Sie über P -vollständigkeit sprechen, weil this means different things to different people basierend auf welche Art von Kürzungen Sie erlauben. Ich gehe davon aus, dass Sie Polynomzeit-Reduktionen verwenden. Wählen Sie in diesem Fall eine andere Sprache als L & l; ∈ P; oder {a, b}*. Wählen Sie jetzt eine Sprache M in P, die Sie mögen. Hier ist eine dumme Reduktion von M bis L:
- eine Eingabezeichenfolge w gegeben, entscheiden, ob w in M in Polynomzeit (dies ist möglich, weil M ∈ P.)
- Wenn w ∈ M, Ausgang eine beliebige Zeichenfolge w ∈ L, die Sie möchten (mindestens eine existiert, weil L nicht leer ist.)
- Sonst w ∉ M, also geben Sie eine beliebige Zeichenfolge aus w ∉ L, die Sie möchten (mindestens eine existiert, weil L ist nicht
{a, b}*.
Diese Reduktion dauert Polynom Zeit, da jeder Schritt Polynom Zeit in Anspruch nimmt, so ist es eine Reduktionspolynoms Zeit von einer beliebigen P Sprache L. Daher L P -komplette in Bezug auf Polynom-Zeitverkürzungen. Wenn Sie über Vollständigkeitsvorstellungen sprechen, müssen Sie im Allgemeinen sicherstellen, dass Ihre Reduktionen weniger Rechenressourcen erhalten als die Klasse der Solver, die Sie verwenden, oder Sie können seltsame Dinge tun, wie hier beschrieben machen Reduktionen im Wesentlichen nutzlos.
Gibt es einen Kontext in der Frage fehlt? P ist eine Klasse von Entscheidungsproblemen, aber '{}' und '{a, b} *' sehen nicht wie Entscheidungsprobleme aus. (Sie können auch finden, dass cs.stackexchange ein besserer Ort für diese Frage ist, da es sich nicht auf das Programmieren bezieht). –
Nur ein Tipp: http://cs.stackexchange.com/ vielleicht besser geeignet für diese Frage (also einfacher, eine Antwort zu bekommen) – shole
@PaulHankin '{}' und '{a, b} *' sind Akzeptoren für Sprachen I glauben. Der erste lehnt jede Eingabe ab. Die zweite akzeptiert jede Eingabe unter der Annahme, dass die Sprache nur aus dem Symbol a und b besteht. – aste123