by Dimitri P. Bertsekas. / Includes bibliographies. / Research supported by National Science Foundation Grant ENG-79-06332 (87649)

Report covers June 1, 1976-July 31, 1978. / Each v. has also a distinctive title. / National Science Foundation. Grant NSF/RANN APR76-12036 National Science Foundation. Grant DAR78-17826

Report covers June 1, 1976-July 31, 1978. / Each v. has also a distinctive title. / National Science Foundation. Grant NSF/RANN APR76-12036 National Science Foundation. Grant DAR78-17826

Report covers June 1, 1976-July 31, 1978. / Each v. has also a distinctive title. / National Science Foundation. Grant NSF/RANN APR76-12036 National Science Foundation. Grant DAR78-17826

Report covers June 1, 1976-July 31, 1978. / Each v. has also a distinctive title. / National Science Foundation. Grant NSF/RANN APR76-12036 National Science Foundation. Grant DAR78-17826

Report covers June 1, 1976-July 31, 1978. / Each v. has also a distinctive title. / National Science Foundation. Grant NSF/RANN APR76-12036 National Science Foundation. Grant DAR78-17826

Report covers June 1, 1976-July 31, 1978. / Each v. has also a distinctive title. / National Science Foundation. Grant NSF/RANN APR76-12036 National Science Foundation. Grant DAR78-17826

Report covers June 1, 1976-July 31, 1978. / Each v. has also a distinctive title. / National Science Foundation. Grant NSF/RANN APR76-12036 National Science Foundation. Grant DAR78-17826

In this thesis we explore a number of ways in which combinatorial games can be used to help prove results in the area of propositional proof complexity. The results in this thesis can be divided into two sets, the first being dedicated to the study of Resolution space (memory) requirements, whereas the second is centered on formalizing the notion of `dangerous' reductions. The first group of results investigate Resolution space measures by asking questions of the form, `Given a formula F and integer k, does F have a [Type of Resolution] proof with [Type of Resource] at most k?'. We refer to this as a proof complexity resource problem, and provide comprehensive results for several forms of Resolution as well as various resources. These results include the PSPACE-Completeness of Tree Resolution clause space (and the Prover/Delayer game), the PSPACE-Completeness of Input Resolution derivation total space, and the PSPACE-Hardness of Resolution variable space. This research has theoretical as well as practical motivations: Proof complexity research has focused on the size of proofs, and Resolution space requirements are an interesting new theoretical area of study. In more practical terms, the Resolution proof system forms the underpinnings of all modern SAT-solving algorithms, including clause learning. In practice, the limiting factor on these algorithms is memory space, so there is a strong motivation for better understanding it as a resource. With the second group of results in this thesis we investigate and formalize what it means for a reduction to be `dangerous'. The area of SAT-solving necessarily employs reductions in order to translate from other domains to SAT, where the power of highly-optimized algorithms can be brought to bear. Researchers have empirically observed that it is unfortunately possible for reductions to map easy instances from the input domain to hard SAT instances. We develop a non-Hamiltonicity proof system and combine it with additional results concerning the Prover/Delayer game from the first part of this thesis as well as proof complexity results for intuitionistic logic in order to provide the first formal examples of harmful and beneficial reductions, ultimately leading to the development of a framework for studying and comparing translations from one language to another.

The present thesis is dedicated to two topics in Dynamics of Holomorphic maps. The first topic is dynamics of simple parabolic germs at the origin. The second topic is Polynomial-time Computability of Julia sets.\\ Dynamics of simple parabolic germs. Let $F$ be a germ with a simple parabolic fixed point at the origin: $F(w)=w+w^2+O(w^3).$ It is convenient to apply the change of coordinates $z=-1/w$ and consider the germ at infinity $$f(z)=-1/F(-1/z)=z+1+O(z^{-1}).$$ The dynamics of a germ $f$ can be described using Fatou coordinates. Fatou coordinates are analytic solutions of the equation $\phi(f(z))=\phi(z)+1.$ This equation has a formal solution \[\tilde\phi(z)=\text{const}+z+A\log z+\sum_{j=1}^\infty b_jz^{-j},\] where $\sum b_jz^{-j}$ is a divergent power series. Using \'Ecalle's Resurgence Theory we show that $\tilde$ can be interpreted as the asymptotic expansion of the Fatou coordinates at infinity. Moreover, the Fatou coordinates can be obtained from $\tilde \phi$ using Borel-Laplace summation. J.~\'Ecalle and S.~Voronin independently constructed a complete set of invariants of analytic conjugacy classes of germs with a parabolic fixed point. We give a new proof of validity of \'Ecalle's construction. \\ Computability of Julia sets. Informally, a compact subset of the complex plane is called \emph if it can be visualized on a computer screen with an arbitrarily high precision. One of the natural open questions of computational complexity of Julia sets is how large is the class of rational functions (in a sense of Lebesgue measure on the parameter space) whose Julia set can be computed in a polynomial time. The main result of Chapter II is the following: Theorem. Let $f$ be a rational function of degree $d\ge 2$. Assume that for each critical point $c\in J_f$ the $\omega$-limit set $\omega(c)$ does not contain either a critical point or a parabolic periodic point of $f$. Then the Julia set $J_f$ is computable in a polynomial time.