ALT 2002, the 13th International Conference on Algorithmic Learning TheoryMövenpick Hotel, Lübeck, Germany, November 24 - 26, 2002
Ein Constraint-Satisfaction-Problem (CSP) besteht aus einer Folge von Einschränkungen an einen Vektor von Variablen. Eine Lösung eines CSPs ist eine Belegung der Variablen, die alle Einschrðnkungen erfüllt. Wir untersuchen Boolesche Constraint-Satisfaction-Probleme, bei denen als Einschrðnkungen beliebige Boolesche Relationen verwendet werden dürfen.
Thomas Schaefer erzielte im Jahre 1978 ein bemerkenswertes Resultat: Er konnte zeigen, dass für jede mögliche Menge von erlaubten Constraints das Problem, von einem CSP festzustellen, ob es eine Lösung besitzt, entweder NP-vollständig ist oder in Polynomialzeit lösbar ist (und nicht etwa in einem der -- unter der Annahme P ungleich NP existierenden -- unendlich vielen Zwischengrade liegt). Neben diesem sog. Erfüllbarkeitsproblem wurden seitdem viele weitere Fragestellungen über CSPs komplexitätstheoretisch klassifiziert.
Im Vortrag wird nach einer Einführung in das Themengebiet der Booleschen Constraint-Satisfaction-Probleme die Fragestellung untersucht, wie schwierig es ist, festzustellen, ob zwei gegebene CSPs die gleiche Menge von Lösungen besitzen.
For this talk werepresent knowledge simply as computer program. A program for a function f represents knowledge of how to compute f - and it may contain additional information, perhaps implicit and needing to be extracted. Our setting is Gold-style computational learning theory in which all the data points from the graph of a function f are successively fed into an algorithmic learning device, and that device outputs a corresponding sequence of computer programs - in the ``hope'' those output programs will converge to a program or programs which successfully compute f. Investigated are some surprising and delicate tradeoffs between the generality of an algorithmic learning device and the quality of the successful programs it converges to. Two classes of results are presented. There are results to the effect that, with small increases in generality of the learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal. Importantly, there are also results in which the complexity of successfully learned programs is optimal and the learning device is quite general, but some of those optimal, learned programs are provably unalterably information deficient - in fact, deficient as to safe, algorithmic extractability of even the fact that they are approximately optimal. For these results, the safe, algorithmic methods of information extraction will be by proofs in arbitrary, true, recursively axiomatizable extensions of Peano Arithmetic. This is joint work with Keh-Jian Chen, James Royer, and Sanjay Jain.
