The infimal prefix-closed, controllable, and observable superlanguage plays an essential role in the relationship between controllability, observability, and co-observability-the central notions of supervisory control theory. Existing algorithms for its computation are exponential and it is not known whether a polynomial algorithm exists. We answer the question by studying the state complexity of this language. State complexity of a language is the number of states of its minimal deterministic finite automaton (DFA). For a language with state complexity n, we show that the upper bound state complexity on the infimal prefix-closed and observable superlanguage is 2(n) + 1 and that this bound is asymptotically tight. Hence, there is no algorithm computing a DFA of the infimal prefix-closed and observable superlanguage in polynomial time. Our construction shows that such a DFA can be computed in time O(2(n)). The construction involves nondeterministic finite automata (NFAs) and a computation of the supremal prefix-closed sublanguage. We study the computation of supremal prefix-closed sublanguages and show that there is no polynomial-time algorithm computing an NFA of the supremal prefix-closed sublanguage of a language given as an NFA even if the language is unary.