Komplexität des Problems der Wörter mit den wenigsten Buchstaben, die von einem endlichen Automaten akzeptiert werden

Wenn ein endlicher (deterministischer oder nicht deterministischer) Automat A und ein Schwellenwert n gegeben sind , akzeptiert A ein Wort, das höchstens n verschiedene Buchstaben enthält?

(Mit k verschiedenen Buchstaben meine ich, dass aabaa zwei verschiedene Buchstaben hat, a und b .)

Ich habe gezeigt, dass dieses Problem NP-vollständig ist, aber meine Reduktion erzeugt Automaten, in denen derselbe Buchstabe auf vielen Übergängen erscheint.

Mich interessieren eher die Fälle, in denen jeder Buchstabe höchstens k- mal in A vorkommt, wobei k ein fester Parameter ist. Ist das Problem noch NP-vollständig?

Für k = 1 ist das Problem nur der kürzeste Weg, ebenso wie für P. Für k = 2 konnte ich weder eine Zugehörigkeit zu P nachweisen noch einen Beweis für die NP-Härte finden.

Irgendeine Idee, zumindest für k = 2?

cc.complexity-theory np-hardness automata-theory David Monniaux
quelle

Für

sollten Sie die Ergebnisse zum Matroid-Paritätsproblem untersuchen: en.wikipedia.org/wiki/Matroid_parity_problem

k = 2

$k=2$

domotorp

Antworten:

Es ist NP-schwer für . Die Reduktion erfolgt von 3-SAT- (2,2), dh jede Klausel enthält Literale und jedes Literal kommt in höchstens Klauseln vor. $k=3$ $3$ $2$

$k$ $st$ $n$

$s$ $n$ $n$ $2n$ $n$

domotorp
quelle

Dies ist die Reduktion, die ich verwendet habe (aus CNF-SAT), aber ich wusste nicht, dass 3-SAT- (2,2) auch NP-vollständig ist, daher meine Bemerkung über Buchstaben, die möglicherweise oft vorkommen. Vielen Dank!

David Monniaux

Und tatsächlich (ich hätte darüber nachdenken sollen!) Ist eine Reduzierung von SAT auf 3-SAT- (2,2) nur geringfügig komplizierter als die übliche Reduzierung auf 3CNF-SAT!

David Monniaux