The thesis consists of two parts. In both parts, the problems studied are of significant interest, but are either _NP_-hard or unknown to be polynomially decidable. Realistically, this forces us to relax the objective of optimality or restrict the …
We partially solve an additive combinatorial problem and then use it to construct optimal pairing strategies for certain generalised Tic-Tac-Toe games.
Generalizations and applications of Alon's Nullstellensatz are discussed. Several proof techniques are collected, and a common generalization of two Nullstellensätze is given (though retrospectively this result is not useful at all).