We examine the completeness problem for Modal Logic: given a formula, is it complete? We discover that for most cases, completeness and validity have the same complexity, with certain exceptions for which there are, in general, no complete formulas. To prove upper bounds, we give a game which combines bisimulation games and tableaux, and which determines whether a formula is complete. The game then easily turns into an alternating algorithm.
['Antonis Achilleos']
The Completeness Problem for Modal Logic