  We study the computational complexity of the non-preemptive scheduling
problem of a list of independent jobs on a set of identical parallel processors
with a makespan minimization objective. We make a maiden attempt to explore the
combinatorial structure showing the exhaustive solution space of the problem by
defining the \textit{Scheduling Solution Space Tree (SSST)} data structure. The
properties of the \textit{SSST} are formally defined and characterized through
our analytical results. We develop a unique technique to show the problem
$\mathcal{NP}$ using the SSST and the \textit{Weighted Scheduling Solution
Space Tree (WSSST)} data structures. We design the first non-deterministic
polynomial-time algorithm named \textit{Magic Scheduling (MS)} for the problem
based on the reduction framework. We also define a new variant of
multiprocessor scheduling by including the user as an additional input
parameter. We formally establish the complexity class of the variant by the
reduction principle. Finally, we conclude the article by exploring several
interesting open problems for future research investigation.
