Bedingungserfüllungsprobleme: jenseits des endlichen Falles

Bei einem Bedingungserfüllungsproblem sind eine endliche Menge von Variablen sowie Bedingungen an diese gegeben; die Frage ist, ob es eine Lösung für die Variablen gibt, also ob man den Variablen Werte so zuordnen kann, dass alle Bedingungen erfüllt werden . In diesem Projekt konzentrieren wir uns ausschliesslich auf Bedingungserfüllungsprobleme, bei denen eine Menge von erlaubten Werten für die Variablen, sowie die Art der erlaubten Bedingungen, vorher festgelegt sind. Ein Beispiel ist das Problem, bei dem Variablen sowie ein lineares Gleichungssystem mit rationalen Koeffizienten, in dem die Variablen vorkommen, gegeben sind; die Gleichungen des Systems sind also die Bedingungen an die Variablen. Ob ein solches System eine Lösung mit rationalen Werten für die Variablen hat, kann mit dem Algorithmus von Gauß entschieden werden. Ein weiteres Beispiel ist das Problem der Lösbarkeit eines verallgemeinerten Sudokus, also eines Quadrates der Größe (n2)x(n2), wobei n eine natürliche Zahl ist, bei dem einige Felder mit natürlichen Zahlen vorausgefüllt sind; die Frage ist, ob die leeren Felder den Regeln des Sudoku entsprechend mit natürlichen Zahlen vervollständigt werden können. Hier entsprechen die leeren Felder also den Variablen, und die Bedingungen werden dur ch die Sudoku-Regeln gestellt; die erlaubten Werte für die Variablen sind die natürlichen Zahlen. Ein drittes Beispiel ist das Problem, bei dem Variablen gegeben sind sowie Bedingungen, welche besagen, dass eine bestimmte Variable echt kleiner sein muss a ls eine bestimmte andere Variable; die Frage ist, ob man den Variablen natürliche Zahlen so zuordnen kann, dass alle Bedingungen erfüllt werden. Wie man leicht einsieht, ist dies genau dann möglich, wenn die Bedingungen nicht erzwingen, dass eine Variable echt kleiner ist als sie selbst. Das fundamentale Ziel dieses Projektes ist es, jene Bedingungserfüllungsprobleme, welche effizient von einem Algorithmus gelöst werden können, von jenen zu unterscheiden, für welche dies nicht der Fall ist; hier setzen wir effizient mit in Polynomialzeit gleich, was bedeutet, dass es ein festes Polynom p(n) gibt, sodass der Algorithmus die Antwort nach p(n) Schritten liefert, wenn n Variablen gegeben sind. Von den drei oben angeführten Beispielen können nur das erste und das dritte effizient gelöst werden, es sei denn, das bekannte P=NP Milleniumsproblem hat eine positive Antwort. Ist die erlaubte Wertemenge für die Variablen endlich, also beispielsweise wenn die Variablen einen der Wahrheitswerte 0 oder 1 annehmen müssen, dann wissen wir genau, welche Bedingungserfüllungsprobleme sich effizient lösen lassen: diese haben nämlich eine klare strukturelle Beschreibung. In diesem Projekt wollen wir eine ähnliche Beschreibung für bestimmte Bedingungserfüllungsprobleme, bei denen die Variablen Werte in einer unendlichen Menge annehmen können, erreichen.