Wenn es keine Reduzierung von A bis B gibt

Question

Ich bin auf der folgenden Frage:

wenn es keine $

Answer 1

Die Sprache $ A $ ist nicht unbedingt unentschieden, wenn wir beliebige, aber feste Wahl des $ B $ . Zum Beispiel Set $ B $ , um die leere Sprache zu sein. Die einzige Sprache, die für $ B $ reduziert ist, ist $ B $ it selbst.

Andererseits, wenn Sie damit meinen, dass es gibt, gibt es eine Sprache $ B $ so, dass $ a \ leq_m b $ , dann für jede Sprache $ A $ Egal, ob es entschieden ist oder nicht, dass es einen solchen $ gibt B $ , nämlich wählen Sie $ B $ , um die Sprache $ A $ it selbst zu sein.

Beachten Sie, dass die einzige sinnvolle Möglichkeit, die Anweisung zu lesen, zu reparieren, $ B $ in eine Sprache, die für die Klasse der entgabelnden Sprachen abgeschlossen ist. Deutlich werden entschiedene Sprachen unter $ \ LEQ_M $ Reduktionen geschlossen. Ich denke jedoch nicht, dass eine vollständige Sprache für diese Klasse bekannt ist (oder ob eine solche Sprache sein kann) gebaut). Für eine solche Sprache $ B $ , ist eine Sprache $ A $ entgreift, wenn und nur wenn < Span-Klasse="Math-Container"> $ A \ leq_m B $ pro Definition von vollständigen Sprachen.