A king in a directed graph is a node from which each node in the graph can be reached via 
paths of length at most two.  There is a broad literature on tournaments (completely oriented digraphs), 
and it has been known for more than half a century that all tournaments have at least one king.  
Recently, kings have proven useful in theoretical computer science, in particular in the study of 
the complexity of the semifeasible sets and in the study of the complexity of reachability problems.
In this paper, we study the complexity of recognizing kings.  For each succinctly specified family of 
tournaments, the king problem  is known to belong to Pi2.
We prove that this bound is optimal:  We construct a succinctly specified tournament family whose 
king problem is Pi2-complete.  It follows easily from our proof approach that the problem  of testing 
kingship in succinctly specified graphs (which need not be tournaments) is Pi2-complete.
We also obtain Pi2-completeness results for k-kings in succinctly specified j-partite tournaments, 
k,j g.e. 2, and we generalize our main construction to show that Pi2-completeness holds for testing 
k-kingship in succinctly specified families of tournaments for all k g.e. 2.<BR>
* This report appear
as a technical/research report at U.R., Tokyo Tech, and the Computing Research Repository.