Monadische Erweiterungen von monadic NP

Fagin zeigt in seiner bahnbrechenden Arbeit, dass die Komplexitätsklasse NP mit der logischen Sprache 'existentielle Logik zweiter Ordnung' identifiziert werden kann. Ein einfaches und daher greifbares Fragment dieser Sprache ist monadic NP. Fagin bezeichnet monadic NP als '...training ground for attacking the problems in their full generality'. In dieser Arbeit werden zwei Arten von monadischen Erweiterungen von monadic NP untersucht. Der erste Teil beschäftigt sich mit schwachen built-in Relationen.Einebuilt-in Relation B heißt schwach, falls: monadic NP + B + polynomielles Padding neq NP.Es werden zwei neue Klassen schwacher built-in Relationen (unendlich teilbare-und verpackbare built-in Relationen) eingeführt. Hauptergebnis dieses Teils ist eine Klassifizierung aller bekannten schwachen built-in Relationen mittels dieser beiden Klassen. Im zweiten Teil dieser Arbeit werden monadische Abschlüsse von monadic NP betrachtet. Besonderes Interesse gilt dabei den positiven Abschluss erster Ordnung von monadic NP (kurz: PFO(monNP)). Hauptergebnis dieses Teils ist die Aussage, dass nicht-k-Färbbarkeit (k=>3) nicht ausdrückbar ist in PFO(monNP).

Higher-order perturbative relativistic corrections to energies and properties

Relativistic effects need to be considered in quantum-chemical calculations on systems including heavy elements or when aiming at high accuracy for molecules containing only lighter elements. In the latter case, consideration of relativistic effects via perturbation theory is an attractive option. Among the available techniques, Direct Perturbation Theory (DPT) in its lowest order (DPT2) has become a standard tool for the calculation of relativistic corrections to energies and properties.In this work, the DPT treatment is extended to the next order (DPT4). It is demonstrated that the DPT4 correction can be obtained as a second derivative of the energy with respect to the relativistic perturbation parameter. Accordingly, differentiation of a suitable Lagrangian, thereby taking into account all constraints on the wave function, provides analytic expressions for the fourth-order energy corrections. The latter have been implemented at the Hartree-Fock level and within second-order Møller-Plesset perturbaton theory using standard analytic second-derivative techniques into the CFOUR program package. For closed-shell systems, the DPT4 corrections consist of higher-order scalar-relativistic effects as well as spin-orbit corrections with the latter appearing here for the first time in the DPT series.Relativistic corrections are reported for energies as well as for first-order electrical properties and compared to results from rigorous four-component benchmark calculations in order to judge the accuracy and convergence of the DPT expansion for both the scalar-relativistic as well as the spin-orbit contributions. Additionally, the importance of relativistic effects to the bromine and iodine quadrupole-coupling tensors is investigated in a joint experimental and theoretical study concerning the rotational spectra of CH2BrF, CHBrF2, and CH2FI.