Erwin Engeler was born in Schaffhausen on 13 February 1930 a citizen of Wagenhausen (Thurgovia). He attended school in Diessenhofen (TG) and Schaffhausen and looks back on his various schools warmly as having provided a conducive environment. His schoolwork also left him time for other activities. For one, he pursued a career as a boy scout which he crowned by attaining the position of Rover Commissary of all Thurgovia. For another, he was an avid client of the municipal library of Schaffhausen. One book which he found there was Hilbert-Bernays' ‘Grundlagen der Mathematik’. One wonders what Erwin would have said if a soothsayer had told him that the author's own copy would one day be passed on to him by the late Bernays' family.

A function f is defined, mapping graphs with n vertices onto graphs with vertex set {1,...,n} . f(X) is isomorphic to X and X is isomorphic to Y iff f(X) = f(Y). For each d, the restriction of f to graphs of valence d is computable in time O(nτ(d)) for a suitable integer τ(d).

A conjunctive-normal-form expression (cnf) IS said to be 2-satisfiable if and only if any two of its clauses are simultaneously satisfiable It is shown that every 2-satisfiable cnf has a truth assignment that satisfies at least the fraction h of its clauses, where h = (x/5 -1)/2 ~ 0.618 (the reciprocal of the "golden ratio").The proof ~s constructive m that it provides a polynomtal-ume algorithm that will find for any 2-sausfiable cnf a truth assignment satisfying at least the fraction h of its clauses.Furthermore, this result is optimal m that the constant h IS as large as possible.It is shown that, for any rational h' > h, the set of all 2-satisfiable cnfs that have truth assignments satisfying at least the fraction h' of their clauses ~s an NP-complete set gEY WORDS AND PHRASES doubly transltwe permutations, golden mean, NP-complete, polynomial enumeration algorithm, polynomially constructive reductions, satlsfiabdlty CR CATEGORIES 5.21, 5.25, 5.39

A conjunctive normal form (cnf) is 2-satisfiable, iff any 2 of its clauses are satisfiable. It is shown that every 2-satisfiable cnf s has an interpretation which satisfies at least h·length(s) clauses (h=(√5-1)/2∼0.618). This result is optimal, insofar as the given constant h is maximal. The proof is polynomially constructive, i.e., it yields a polynomial algorithm, which computes an interpretation satisfying h·length(s) clauses for the 2-satisfiable cnf's s. Moreover, if h

Nach allgemeiner Ueberzeugung können gewisse Sätze der Analysis nicht konstruktiv bewiesen werden. Man denke etwa an den folgenden Satz: Eine monotone und beschränkte Folge a(n) von rationalen Zahlen konvergiert, d.h. es gibt eine solche ganzzahlige Funktion k(m), daß Unter einem konstruktiven Beweis dieses Satzes hätte man etwa die Angabe eines Verfahrens zu verstehen, das gestattet, die Funktion k(m) auf Grand der Folge a(n) rekursiv zu definieren. Wenn ein solcher Beweis vorläge, wäre insbesondere gezeigt, daß es zu einer rekursiv definierten Folge a(n) mit den verlangten Eigenschaften stets eine rekursiv definierbare Konvergenzfunktion k(m) gibt. Es soil nun im folgenden von einigen grundlegenden Sätzen der reellen Analysis gezeigt werden, daß sie nicht konstruktiv bewiesen werden können—konstruktiv in dem Sinn, der eben angedeutet wurde. Wir stützen uns dabei auf die Begriffe der rekursiven und der berechenbaren Funktion; rekursive und berechenbare Funktionen sind zahlentheoretische Funktionen. Unter einer rekursiven Funktion möge vorläufig eine primitiv rekursive Funktion verstanden werden (vgl. etwa D. Hilbert und P. Bernays [3], S.286); berechenbar meint berechenbar im Sinne von A. Church [1], S. C. Kleene [4], A. M. Turing [6]. Der Begriff der “konstruktiv definierten Funktion” wird durch die Bestimmung als “rekursive Funktion” eher eng, durch die Bestimmung als “berechenbare Funktion” eher weit gefaßt. Definition I. Eine Folge rationaler Zahlen Φ(n) heißt rekursiv,(berechenbar), wenn es solche rekursiven (berechenbaren) Funktionen ϕ{n), ψ(n) und χ(n) gibt, daß χ(n) ≧1 und . Definition II. Eine Folge Φ(n) von rationalen Zahlen heißt rekursiv (berechenbar) konvergent, wenn es eine solche rekursive (berechenbare) Funktion v(m) gibt, daß Wir werden zeigen (Satz I): Es gibt eine rekursive, monotone und beschränkte Folge rationaler Zahlen, die nicht berechenbar konvergiert. Bei unserer Auffassungsweise ist darin enthalten, daß der zu Beginn erwähnte Satz nicht konstruktiv bewiesen werden kann.