  In this paper, functional observability and detectability, structural
functional observability (SFO), and the related sensor placement problems are
investigated. A new concept of modal functional observability coinciding with
the notion of modal observability is proposed. This notion introduces new
necessary and sufficient conditions for functional observability and
detectability without using system observability decomposition and facilitates
the design of a functionally observable/detectable system. Afterwards, SFO is
redefined rigorously from a generic perspective, contrarily to the definition
of structural observability. A new and complete graph-theoretic
characterization for SFO is proposed. Based on these results, the problems of
selecting the minimal sensors from a prior set to achieve functional
observability and SFO are shown to be NP-hard. Nevertheless, supermodular set
functions are established, leading to greedy heuristics that can find
approximation solutions to these problems with provable guarantees in
polynomial time. A closed-form solution along with a constructive procedure is
also given for the unconstrained case on systems with diagonalizable state
matrices. Notably, our results also yield a corollary: polynomial time
verification of the structural target controllability of $n-1$ state variables
is achievable, where $n$ is the system state dimension, a problem that may be
hard otherwise.
