\documentclass{acm_proc_article-sp}

\begin{document}

\title{On the Computational Complexity of \\ Designing and Reconfiguring \\ Component-based Software Systems}
%\subtitle{[Extended Abstract]}

\numberofauthors{2} 

\author{
\alignauthor Todd Wareham \titlenote{Corresponding Author} \\
       \affaddr{Department of Computer Science} \\
       \affaddr{Memorial University of Newfoundland}\\
       \affaddr{St.\ John's, NL Canada}\\
       \email{harold@mun.ca}
\alignauthor Marieke Sweers \\
       \affaddr{Radboud University Nijmegen} \\
       \affaddr{Donders Institute for Brain, Cognition, and Behaviour} \\
       \affaddr{Nijmegen, The Netherlands}
       \email{marieke.sweers@gmail.com}
}

\maketitle
\begin{abstract}
Though Component-Based Development (CBD) is a popular approach to mitigating
the costs of creating software systems, it is not clear to what
extent CBD is preferable to other approaches
to software engineering or to what extent the core component selection
and adaptation activities of CBD can be implemented to operate 
without human intervention
in an efficient and reliable manner. In this paper, we use computational 
complexity analysis
to compare the computational characteristics of software system design
and reconfiguration by {\em de novo} design, component selection, and
component selection with adaptation. Our results show that none of these
approaches can be implemented to operate both efficiently and reliably either
in general or relative to a surprisingly large number of restrictions on
software system, component, and component library structure. We also give 
the first restrictions under which all of these approaches can be
implemented to operate both efficiently and reliably.
\end{abstract}

% A category with the (minimum) three required fields
\category{D.2.13}{Software Engineering}{Resuable Software}[Reuse models]
\category{D.2.2}{Software Engineering}{Design Tools and Techniques}
\category{F.2.2}{Analysis of Algorithms and Problem Complexity}{Nonnumerical algorithms and problems}[computations on discrete structures]
%A category including the fourth, optional field follows...

\terms{Algorithms, Design, Measurement, Performance, Theory}

\keywords{component-based development, parameterized computational complexity} % NOT required for Proceedings

\newcommand{\lb}{}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\nolb}{\nolinebreak}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newdef{definition}{Definition}

\section{Introduction}

\label{SectIntro}

Component-based development (CBD) is a popular approach to mitigating
the monetary and time costs of creating and maintaining software
systems \cite{AF97,Bro00,HC01}. In CBD, previously-developed software modules 
called components are stored in libraries and connected together (possibly
with some adaptation of the component code and architecture) as needed to
generate new software systems from given requirements. Over the last 20 years,
a number of technologies have been implemented to assist human programmers in 
creating com- ponent-based systems, {\em e.g.}, CORBA, CCM, EJB, COM+, and 
much effort has been put into automating the key CBD activities 
of component selection and adaptation.

There are two ongoing issues of great importance in the CBD community:
(1) the circumstances (if any) under which the cost of selecting and adapting 
components is less than the cost of developing software systems from scratch,
{\em i.e.}, {\em de novo}
\cite{GT05} and (2) the need for CBD to operate fully automatically and 
efficiently to accommodate ubiquitous and autonomic computing systems which need
to create and reconfigure software without or with minimal human intervention 
at runtime \cite{FK05,MV14}. To address these issues, it would be most
useful to know if efficient and reliable methods are available for selecting and
adapting components in CBD and, if so, under what circumstances these methods 
outperform other approaches to software engineering.

In this paper, we present results addressing both of these questions.
First, using computational complexity analysis \cite{GJ79}, we 
show that both creating and reconfiguring software systems either by
{\em de novo} design, component selection, or component selection with 
adaptation are all $NP$-hard and thus intractable in general. 
% This holds even 
% in the case of basic software system, component, and component library 
% models. 
Second, using parameterized complexity analysis 
\cite{DF13}, we give restrictions under which all of these 
activities are tractable and prove that surprisingly few restrictions on 
either software system structure or the allowable degree of 
adaptation render these activities tractable. Though these
results are derived relative to basic models of 
software systems and components, we show
that they also apply to more realistic models.

The remainder of this paper is organized as follows. In Section 
\ref{SectFormCBS}, we present our software system, component, and
component library models and formalize the problems of {\em de novo} and
component-based software system design and reconfiguration relative
to these models.  Section \ref{SectCIRes} demonstrates the intractability of 
all of these problems in general. Section \ref{SectTCM} describes a 
methodology for identifying conditions for tractability, which is then applied 
in Section \ref{SectTCRes} to identify such conditions for our problems.
In order to accommodate conference page limits and focus in the main text on 
the implications of our results for CBD, proofs
of selected results are given in Appendix \ref{AppProof}. Finally, our
conclusions and directions for future work are given in Section \ref{SectConc}.

\subsection{Related Work}

Computational complexity analyses of the component selection problem have
been done previously \cite{BBR05, PO99,PWM03}. However, the formalizations
used in these analyses focused on the
satisfaction of sets of desired system objectives, and did not include 
specifications of software system and component structure that are detailed 
enough to investigate the conditions under which restrictions
on these structures would make component selection
tractable. They also did not address the issue of component adaptation.

\section{Formalizing Component-based \\ Design and Reconfiguration}

\label{SectFormCBS}

Our goal in this paper is to assess whether or not component-based
development has advantages over conventional
software engineering relative to different activities in the software
life cycle. This assessment can be stated most simply
along two dimensions:

\begin{enumerate}
\item{
\textit{Software design mode}: creating software using only
components drawn from component libraries versus 
creating software by adapting components drawn from component
libraries or creating software {\em de novo}
that is organized in a specified component-like fashion.
}
\item{
\textit{Software lifecycle activity}: designing the initial version of
a software system relative to a set of requirements versus reconfiguring
an existing system to accommodate one or more changes to the requirements.
}
\end{enumerate}

\noindent
The possibilities implicit in these dimensions result in the following
six informal computational problems:

\noindent
{\sc Software Design} \\
{\em Input}: Software requirements $R$, software-structure specification $X$ \\
{\em Output}: A software system $S$ whose structure is consistent with $X$
               and whose operation satisfies $R$.

\noindent
{\sc Software Design from Adapted Components} \\
{\em Input}: Software requirements $R$, a set of software-component libraries
              $\cal{C}$ $= \{C_1, C_2, \ldots, C_{|C|}\}$. \\
{\em Output}: A software system $S$ whose structure consists of connected 
               components derived  from components drawn from the libraries in 
               $\cal{C}$ and whose operation satisfies $R$.

\noindent
{\sc Software Design from Components} \\
{\em Input}: Software requirements $R$, a set of software-component libraries
              $\cal{C}$ $= \{C_1, C_2, \ldots, C_{|C|}\}$. \\
{\em Output}: A software system $S$ whose structure consists of connected 
               components drawn from the libraries in $\cal{C}$ and 
               whose operation satisfies $R$.

\noindent
{\sc Software Reconfiguration} \\
{\em Input}: A software system $S$ whose structure is consistent with 
              specification $X$ and whose operation satisfies requirements $R$,
              new software requirements $R_{new}$. \\
{\em Output}: A software system $S'$ derived from $S$ whose structure is 
               consistent with $X$ and whose operation satisfies $R \cup R_{new}$.

\noindent
{\sc Software Reconfiguration from \\ Adapted Components} \\
{\em Input}: A software system $S$ whose structure consists of connected
              components from a set of software-component libraries
              $\cal{C}$ $= \{C_1, C_2, \ldots, C_{|C|}\}$ and whose operation
              satisfies requirements $R$, new software requirements $R_{new}$. \\
{\em Output}: A software system $S'$ derived from $S$ whose structure consists
               of connected components derived from components drawn from the 
               libraries in $\cal{C}$ and whose operation satisfies $R \cup R_{new}$.

\noindent
{\sc Software Reconfiguration from Components} \\
{\em Input}: A software system $S$ whose structure consists of connected
              components from a set of software-component libraries
              $\cal{C}$ $= \{C_1, C_2, \ldots, C_{|C|}\}$ and whose operation
              satisfies requirements $R$, new software requirements $R_{new}$. \\
{\em Output}: A software system $S'$ derived from $S$ whose structure consists
               of connected components drawn from the libraries in $\cal{C}$ 
               and whose operation satisfies $R \cup R_{new}$.

To assess the computational difficulty of and (if necessary)
explore algorithmic options for efficiently solving these problems,
we need formalizations of all of the entities comprising these
problems. There is a vast existing literature on various
types of software requirements, system-structures, structure specifications, 
and components and component libraries. We want to avoid introducing spurious 
computational difficulty due to powerful formalisms, as this would complicate the
interpretation our results. Hence, we shall
choose the simplest such formalizations\footnote{
These formalizations are based on those developed in \cite{OS+15,Swe15} to
analyze the computational complexity of the adaptive toolbox theory of
human decision-making \cite{GT99}. 
}
(additional advantages gained
by such a parsimonious approach are given in Section \ref{SectGenRes}):

\begin{figure}[t]
%
\begin{center}
\begin{tabular}{| c || c | c | c | c | c || c |}
\hline
req.\ & $i_1$ & $i_2$ & $i_3$ & $i_4$ & $i_5$ & action \\
\hline\hline
$r_1$ & T & T & T & T & T & $a_2$ \\
\hline
$r_2$ & T & F & F & F & T & $a_1$ \\
\hline
$r_3$ & F & F & F & F & F & $a_2$ \\
\hline
$r_4$ & F & F & F & F & F & $a_2$ \\
\hline
$r_5$ & T & T & T & F & T & $a_3$ \\
\hline
\end{tabular} \\

\vspace*{0.05in}

(a)

\vspace*{0.05in}

{\tt
\begin{tabular}{l l}
procedure p1:                   & procedure p2 \\
~ if $i_4$ then $a_2$           & ~ if $\neg i_2$ then $a_1$ \\
~ else if $\neg i_3$ then $a_1$ & ~ else if $\neg i_4$ then $a_2$ \\
~ else if $i_5$ then $a_3$      & ~ else $a_3$ \\
~ else $a_1$                    & \\
 & \\
procedure p3:                   & procedure p4: \\
~ if $i_4$ then $a_2$           & ~ $a_2$ \\
~ else $a_2$                    & \\
\end{tabular}
} \\

\vspace*{0.05in}

(b)

\vspace*{0.05in}

{\tt
\begin{tabular}{l l}
selector s1:                    & selector s2: \\
~ if $i_1$ then ???             & ~ if * then ??? \\
~ else if $i_5$ then ???        & \\
~ else ???                      & \\
\end{tabular}
}

\vspace*{0.05in}

(c)

\vspace*{0.05in}

{\tt
\begin{tabular}{l l}
system S1:                    & system S2: \\
~ if $i_1$ then call p1         & ~ if * then call p2 \\
~ else if $i_5$ then call p3    & \\
~ else call p4                  & \\
\end{tabular}
}

\vspace*{0.05in}

(d)
\end{center}
\caption{ Example Requirements, Procedures, Selectors, and Software Systems. 
           (a) Software requirements $R = \{r_1, r_2, r_3, r_4, r_5\}$ defined on
           situation-variables $I = \{i_1, i_2, i_3, i_4, i_5\}$ and
           action-set $A = \{a_1, a_2, a_3\}$. (b)
           Four procedures. (c) Two selectors as they would appear in
           a selector-component library with blank procedure calls. (d)
           Two software systems created by instantiating the procedure-calls
           in the selectors from (c) with procedures from (b).
}
%
\label{FigCSS}
\end{figure}

\begin{itemize}
\item{
\textit{Software Requirements}: The requirements 
will be a set $R = \{r_1, r_2, \ldots r_{|R|}\}$ of situation-action pairs 
where each pair $r_j (s_j,a_j)$ consists of a situation $s_j$ defined by a 
particular set of truth-values $s_j = \langle v(i_1), v(i_2), \ldots$
$v(i_{|I|})\rangle$, $v(i_k) \in \{True, False\}$, relative to each of the Boolean 
variables $i_k$ in set $I = \{i_1, i_2, \ldots, i_{|I|}\}$ and an action $a_j$ from
set $A = \{a_1, a_2, \ldots a_{|A|}\}$.
}
\item{
\textit{Software system-structure}: 
We will here consider the simplest possible 
complex structure consisting of a multiple \texttt{IF-THEN-ELSE}
statement block (a {\bf selector}) whose branches are in turn other 
\texttt{IF-THEN-ELSE} statement blocks ({\bf procedures}) whose branches 
execute actions from $A$. Each selector and procedure \texttt{IF-THEN}
condition is a Boolean formula that is either a variable from $I$ 
{\em e.g.}, $i_j$, or its negation, {\em e.g.}, $\neg i_j$. 
Each selector and procedure with one or more situation-variable conditions
terminates in a final \texttt{ELSE} statement. 
In addition, the selector may consist of single special
statement \texttt{IF * THEN} which evaluates to $True$ in all cases
(the default selector) and a procedure may consist of a single executed
action; such selectors and procedures have no associated conditions.
}
\item{
\textit{Software components and component libraries}: Two-level
software systems of the form above consist of two
types of components, selectors and procedures, which shall be
stored in libraries $L_{sel}$ and $L_{prc}$, respectively.
}
\item{
\textit{Software structure specification}: The basic characteristics
of two-level software systems of the form above are
the situation-variable and action sets on which they are based ($I$ and $A$),
the maximum number of conditions allowed in the selector
($|sel|$) and the maximum number of conditions allowed in
any procedure ($|prc|$).
}
\end{itemize}

\noindent
Examples of these entities are given in Figure \ref{FigCSS}.

\noindent
This allows us to formalize various actions and properties in the
problems given above as follows:

\begin{itemize}
\item A software system $S$ is consistent with a structure-specification
       $X = \langle I, A, |sel|, |prc|\rangle$ if it has the two-level 
       structure described above where \texttt{IF-THEN} conditions 
       are (un)negated members of $I$, all procedure-executed
       actions are drawn from $A$, the number of conditions in the 
       selector is at most $|sel|$ , and the number of conditions in each
       procedure is at most $|prc|$. For example, both software-systems
       in Figure \ref{FigCSS}(d) are consistent with $X = \{
       \{i_1, i_2, i_3, i_4, i_5\}, \{a_1, a_2, a_3\}, 2, 3\}$. 
\item A software system $S$ is constructed from components drawn from 
       $\cal{C}$ $= \{C_{sel}, C_{prc}\}$ if the selector-component is from 
       $C_{sel}$ and each procedure-component is from $C_{prc}$. Note that a 
       member of $C_{prc}$ may appear zero, one, or more times in $S$. For
       example, both software systems in Figure \ref{FigCSS}(d) are
       constructed from $\cal{C}$ $= \{\{{\tt s1, s2}\}, \{{\tt p1, p2, p3, p4}\}\}$.
\item The operation of a software system $S$ satisfies requirements $R$ if
       for each situation-action pair $(s,a)$ in $R$, the execution of $S$
       relative to the truth-settings in $s$ results in the execution of $a$.
       For example, software system {\tt S1} in Figure \ref{FigCSS}(d)
       satisfies the requirements in Figure \ref{FigCSS}(a) but 
       software system {\tt S2} does not (because it produces different
       outputs ($a_3$, $a_1$, $a_1$, and $a_2$ respectively) for requirements $r_1$,
       $r_3$, $r_4$, and $r_5$).
\end{itemize}

\vspace*{-0.08in}

%Given all this, we can now state the following formal versions of the six
%problems given at the beginning of this section:
We can now state the following formal problems:

\noindent
{\sc Software Design} (SDes-Spec) \\
{\em Input}: Software-structure specification $X = \langle I, A, |sel|, 
              |prc|\rangle$, software requirements $R$ based on sets $I$ 
              and $A$.  \\
{\em Output}: A software system $S$ whose structure is consistent with $X$
               and whose operation satisfies $R$, if such an $S$ exists, 
               and special symbol $\bot$ otherwise.

\noindent
{\sc Software Design from \\ Adapted Components} (SDes-CompA) \\
{\em Input}: Software requirements $R$ based on sets $I$ and $A$, a set of 
              software-component libraries $\cal{C}$ $= \{C_{sel}, C_{prc}\}$,
              positive integers $d, c_c \geq 0$. \\
{\em Output}: A software system $S$ whose structure consist of connected 
               components derived by at most $c_c$ changes to at most $d$ 
               components drawn from the libraries in $\cal{C}$ and 
               whose operation satisfies $R$, if such an $S$ exists, and special
               symbol $\bot$ otherwise.

\noindent
{\sc Software Design from Components} (SDes-Comp) \\
{\em Input}: Software requirements $R$ based on sets $I$ and $A$, a set of 
              software-component libraries $\cal{C}$ $= \{C_{sel}, C_{prc}\}$,
              a positive integer $d \geq 0$. \\
{\em Output}: A software system $S$ whose structure consist of connected 
               components based on at most $d$ components drawn from the 
               libraries in $\cal{C}$ and whose operation satisfies $R$, 
               if such an $S$ exists, and special symbol $\bot$ otherwise.

\noindent
{\sc Software Reconfiguration} (SRec-Spec) \\
{\em Input}: A software system $S$ whose structure is consistent with 
              specification $X = \langle I, A, |sel|, |prc|\rangle$ and whose operation 
              satisfies requirements $R$, a set $R_{new}$ of new situation-action pairs
              based on $I$ and $A$, a positive integer $c_c \geq 0$. \\
{\em Output}: A software system $S'$ derived by at most $c_c$ changes to $S$ 
               whose structure is consistent with $X$ and whose operation 
               satisfies $R \cup R_{new}$, if such an $S'$ exists, and special symbol
               $\bot$ otherwise.

\noindent
{\sc Software Reconfiguration from \\ Adapted Components} (SRec-CompA) \\
{\em Input}: A software system $S$ whose structure consists of connected
              components from a set of software-component libraries
              $\cal{C}$ $= \{C_{sel}, C_{prc}\}$ and whose operation
              satisfies requirements $R$, a set $R_{new}$ of new situation-action pairs
              based on $I$ and $A$, positive integers 
              $c_l, c_c, d \geq 0$. \\
{\em Output}: A software system $S'$ derived from $S$ by at most $c_l$ 
               component-changes 
               relative to the libraries in $\cal{C}$ and $c_c$ code-changes 
               whose structure consist of at most $d$ types of connected 
               components and whose operation satisfies 
               $R \cup R_{new}$, if such an $S'$ exists, and special symbol $\bot$ 
               otherwise.

\noindent
{\sc Software Reconfiguration from \\ Components} (SRec-Comp) \\
{\em Input}: A software system $S$ whose structure consists of connected
              components from a set of software-component libraries
              $\cal{C}$ $= \{C_{sel}, C_{prc}\}$ and whose operation
              satisfies requirements $R$, a set $R_{new}$ of new situation-action pairs
              based on $I$ and $A$, positive integers 
              $c_l, d \geq 0$. \\
{\em Output}: A software system $S'$ derived from $S$ by at most $c_l$ 
               component-changes relative to the libraries in $\cal{C}$
               whose structure consists of at most $d$ types of connected 
               components and whose operation satisfies $R \cup R_{new}$,
               if such an $S'$ exists, and special symbol $\bot$ otherwise.

\noindent
We have included parameter $d$ in all component-based problems to allow
control over the number of retrievals from libraries.
The two types of adaptation and reconfiguration changes are: (1) 
changes to the system code: changing the 
condition in or action executed by any \texttt{IF-THEN-ELSE} statement 
($c_c$)
and (2) changes to the system component-set: using a different 
selector-component from $C_{sel}$ or changing any used procedure-component to 
another from $C_{prc}$ ($c_l$).
Note in the case of a selector-change, 
both the original and new selector must have the same number of \texttt{IF-THEN}
statements and the procedures called by the original selector are mapped
to the corresponding positions in the new selector.

\section{Component-based Design and Reconfiguration are Intractable}

\label{SectCIRes}

% In this section, we address whether or not component-based design
% and reconfiguration
% can be done efficiently relative to the model described in Section 
% \ref{SectFormCBS}. 
Following general practice in Computer Science \cite{GJ79},
we define tractability
as being solvable in the worst case in time polynomially bounded in the input
size. We show that a problem is not polynomial-time solvable, {\em i.e.},
not in the class $P$ of polynomial-time solvable problems,  by proving it to be
at least as difficult as the hardest problems in problem-class $NP$
(see \cite{GJ79} for details). 

\noindent
{\em Result A}: SDes-Spec, SDes-CompA, SDes-Comp, SRec-Spec, SRec-CompA,
                 and SRec-Comp are $NP$-hard.

\noindent
Modulo the conjecture $P \neq NP$ which is widely believed to be true 
\cite{For09}, the above shows that even the basic versions of 
component-based design and reconfiguration considered here are not solvable in 
polynomial time. This $NP$-hardness hold for problems SRec-Spec and SRec-CompA 
when the new requirements consist of a single situation-action pair.

Two frequently-adopted responses to 
intractability are to consider
poly-time algorithms which generate solutions that (1) approximate within provable 
bounds the wanted solutions, {\em e.g.}, software systems whose structure are 
close to the values specified in $X$ or which satisfy a large proportion of
the requirements in $R$ \cite{NH08}, or (2) are of acceptable quality
most of the time, {\em e.g.}, genetic or simulated annealing algorithms
\cite{HMZ12}.
In the remainder of this paper, we will consider a third option described
in more detail in the next section.

\section{A Method for Identifying \\ Tractability Conditions}

\label{SectTCM}

A computational problem that is intractable for unrestricted inputs may yet be tractable 
for non-trivial restrictions on the input. This insight is based on the observation that 
some $NP$-hard problems can be solved by algorithms whose running time is polynomial
in the overall input size and non-polynomial only in some aspects of the input 
called \textbf{parameters}. 
%In other words, the main part of the input contributes 
%to the overall complexity in a ``good'' way, whereas only the parameters contribute
% to the overall complexity in a ``bad'' way. In such cases, the problem $\Pi$ is said to 
%be fixed-parameter tractable for that respective set of parameters. The 
The following states this idea more formally. 
	
\vspace*{-0.1in}

\begin{definition}
Let $\Pi$ be a problem with parameters $k_1, k_2,$ $\ldots$. Then $\Pi$ is 
said to be {\bf fixed-parameter (fp-) tractable} for parameter-set $K = 
\{k_1, k_2, ...\}$ if there exists at least one algorithm that solves $\Pi$ 
for any input of size $n$ in time $f(k_1, k_2, ...)n^c$, where $f(\cdot)$ is an 
arbitrary function and $c$ is a constant. If no such algorithm exists then 
$\Pi$ is said to be {\bf fixed-parameter (fp-) intractable} for parameter-set $K$.
%
\label{DefFPT}
\end{definition}
	
\vspace*{-0.1in}

\noindent
In other words, a problem $\Pi$ is fp-tractable for a parameter-set $K$ if all 
superpolynomial-time complexity inherent in solving $\Pi$ can be confined to the
 parameters in $K$. 
% In this sense the ``unbounded" nature of the parameters in $K$ can be 
% seen as a reason for the intractability of the unconstrained version of $\Pi$. 

There are many techniques for designing
fp-tractable algorithms \cite{CF+15,DF13}, and fp-intractability is established in a
manner analogous to classical polynomial-time intractability 
by proving a parameterized problem is at least as difficult as the hardest problems in one
of the problem-classes in the $W$-hierarchy $\{W[1], W[2], ...\}$ (see
\cite{DF13} for details). 
Additional results are typically implied by any given result
courtesy of the following lemmas:

\vspace*{-0.1in}

\begin{lemma}
\cite[Lemma 2.1.30]{War99}
If problem $\Pi$ is fp-tractable relative to parameter-set $K$ then $\Pi$ is
       fp-tractable for any parameter-set $K'$ such that $K \subset K'$.
%
\label{LemProp1}
\end{lemma}

\vspace*{-0.1in}

\begin{lemma}
\cite[Lemma 2.1.31]{War99}
If problem $\Pi$ is fp-intract-able relative to parameter-set $K$ then $\Pi$ is
       fp-intractable for any parameter-set $K'$ such that $K' \subset K$.
%
\label{LemProp2}
\end{lemma}

\vspace*{-0.1in}

It follows from the definition of fp-tractability that if an intractable 
problem $\Pi$ is fp-tractable for parameter-set $K$, then $\Pi$ can be efficiently 
solved even for large inputs, provided only that the values of all parameters in $K$ are 
relatively small. 
This strategy has been successfully applied to many
intractable problems
(see \cite{DF13,Ste12} and references). In the 
next section we show how this strategy may be 
used to render component-based design
and reconfiguration tractable.

\section{What Makes Component-based \\ Design and Reconfiguration \\ 
          Tractable?}

\label{SectTCRes}

Our component-based software design and reconfiguration problems have a number 
of parameters whose restriction could render these problems tractable in the 
sense defined in Section \ref{SectTCM}. An 
overview of the parameters that we considered in our fp-tractability analysis 
is given in Table \ref{TabPrm}. These parameters can be divided into three 
groups:

\begin{table}
\caption{Parameters for Component-based Design and Reconfiguration Problems}
\label{TabPrm}
\centering
\begin{tabular}{| c || l | c |}
\hline
\hline
Parameter   & Description & Applicability \\
\hline
$|I|$       & \# situation-variables & All \\
\hline
$|A|$       & \# possible actions & All \\
\hline
$|sel|$     & Max \# selector-conditions & All \\
\hline
$|prc|$     & Max \# procedure-conditions & All \\
\hline
$d$     & Max \# component-types & *-CompA, \\
        & ~~ in software system  & *-Comp \\
\hline\hline
$|L_{sel}|$ & \# selector-components & *-CompA, \\
            & ~~ in selector-library & *-Comp \\
\hline
$|L_{prc}|$ & \# procedure-components & *-CompA, \\
            & ~~ in procedure-library & *-Comp \\
\hline\hline
$|R_{new}|$   & \# new requirements & SRec-* \\
\hline
$c_c$         & Max \# code-changes & *-CompA, \\
              & ~~ allowed         & SRec-Spec \\
\hline
$c_l$         & Max \# component-changes & SRec-CompA, \\
              & ~~ allowed              & SRec-Comp \\
\hline
\end{tabular}
\end{table}

\vspace*{-0.15in}

\begin{enumerate}
\item Restrictions on system and component structure  \\
       ($|I|$, $|A|$, $|sel|$, $|prc|$, $d$);
\item Restrictions on component libraries structure \\ 
       ($|L_{sel}|$, $|L_{prc}|$);  and
\item restrictions on reconfigurability ($|R_{new}|, c_c$, $c_l$).
\end{enumerate}

\vspace*{-0.15in}

\noindent
We will assess the fixed-parameter
tractability of
our problems relative to the parameters in Table \ref{TabPrm} 
(Section \ref{SectCBSRes}), show how these results apply in more general 
settings (Section \ref{SectGenRes}), and discuss the implications of
these results for component-based development (Section \ref{SectDisc}).

\subsection{Results}

\label{SectCBSRes}

Our parameterized intractability results are as follows:

\noindent
\textit{Result B}: SDes-Spec is $W[2]$-hard for $\{ |A|, |sel|, 
                    |prc| \}$ when $|A| = 2$ and $|sel| = 0$.

\noindent
\textit{Result C}: SDes-CompA is $W[2]$-hard for $\{ |A|, |sel|, |prc|, 
                    d,$ $|L_{sel}|, |L_{prc}|, c_c \}$
           when $|A| = d = 2$, $|sel| = 0$, $|L_{sel}| = |L_{prc}| = 1$.

\noindent
\textit{Result D}: SDes-Comp is $W[2]$-hard for $\{ |A|, d, 
                    |L_{sel}| \}$ when $|A| = 2$ and $|L_{sel}| = 1$.

\noindent
\textit{Result E}: SRec-Spec is $W[2]$-hard for $\{ |A|, |sel|, |prc|, 
                    |R_{new}|, c_c \}$ when $|A| = 3$, $|sel| = 0$, and
                    $|R_{new}| = 1$.

\noindent
\textit{Result F}: SRec-CompA is $W[2]$-hard for $\{ |A|, |sel|, |prc|, 
                    d,$ $|L_{sel}, |L_{prc}|, |R_{new}|, c_l, c_c \}$
           when $|A| = 3$, $|R_{new}| = |L_{sel}| = |L_{prc}| = 1$, 
           $d = 2$, and $|sel| = c_l = 0$.

\noindent
\textit{Result G}: SRec-Comp is $W[2]$-hard for $\{ |A|, d, 
                    |L_{sel}| \}$ when $|A| = 3$ and $|L_{sel}| = 1$.

\noindent
At present, we have the following fp-tractability results:

\noindent
\textit{Result H}: SDes-Spec, SDes-CompA, SDes-Comp, SRec-Spec, 
                    SRec-CompA, and SRec-Comp  are fixed-parameter tractable
                    for $\{ |I| \}$.

\noindent
\textit{Result I}: SDes-Comp and SRec-Comp are fixed-parameter tractable for
                    $\{ |sel|, |L_{prc}| \}$.

\noindent
Note that Results B, C, E, F, and H in combination with Lemmas \ref{LemProp1}
and \ref{LemProp2}
completely characterize the parameterized complexity of problems
SDes-Spec, SDes-CompA, SRec-Spec, and SRec-CompA relative to the 
parameters in Table \ref{TabPrm}.
% While we do not yet have such characterizations for problems
% SDes-Comp and SRec-Comp, the results above are a first step in
% this direction.

\subsection{Generality of Results}

\label{SectGenRes}

Our intractability results, though defined relative to 
basic models of software requirements,
software systems, components, and component libraries, have a broad 
applicability. Observe that the models
for which these results hold are in fact restricted versions of more
realistic alternatives, {\em e.g.},

\begin{itemize}
\item software requirements that explicitly list all situations to 
       which software should respond 
       are a special case of more complex requirements
       which are based on compact specifications of software behaviour
       such as finite-state automata or statecharts and/or incorporate
       other required properties of software systems such as degree
       of reliability and response time;
\item two-level selector / procedure software systems that act as
       simple functions are a special case of more complex 
       persistent software systems 
       whose components invoke each other in more complex 
       manners;
\item components consisting of a single condition-statement block 
       procedure without input parameters or return values and which have
       no dependencies on other components are a special case of more 
       complex components consisting of multiple data types and complex 
       procedures which have dependencies on other components such as
       data-type sharing or inheritance; and
\item component libraries that are simply lists of components are
       a special case of component libraries that incorporate 
       component behaviour-specifications and / or metadata
       to aid in selection and adaptation.
\end{itemize}

\noindent
Intractability results for these alternatives then follow 
from the observation that
intractability results for a problem $\Pi$ also hold for any problem $\Pi'$
that has $\Pi$ as a special case (suppose $\Pi$
is intractable; if $\Pi'$ is tractable by algorithm $A$, then $A$ can be used to solve $\Pi$
efficiently, which contradicts the intractability of $\Pi$ --- hence, $\Pi'$
must also be intractable). 

Our fp-tractability results are much more fragile, as innocuous changes to
software requirements, software system, component, or component library
structure may in fact violate assumptions critical to the operation of the 
algorithms underlying these results. Hence, they may only apply to certain
more complex models, and this needs to be assessed on a case-by-case basis.

\subsection{Discussion}

\label{SectDisc}

We have found that designing and reconfiguring software systems by
{\em de novo} design, component selection, and component selection with
adaptation are all $NP$-hard (Result A).  This implies that it is unlikely 
that deterministic polynomial-time methods exist for any of these problems.
It also answers the question of which of
{\em de novo} design, component selection, or component selection with
adaptation is best for creating software systems -- computationally speaking,
all three methods are equally good (or bad) in general.

This $NP$-hardness has interesting additional implications.
It is widely believed that $P = BPP$ 
\cite[Section 5.2]{Wig07} where 
$BPP$ is considered the most inclusive class of problems that can be efficiently 
solved using probabilistic methods (in particular, methods whose probability of
correctness can be efficiently boosted to be arbitrarily close to
probability one). Hence, our results also imply that unless $P = NP$, 
there are no probabilistic polynomial-time methods which correctly design
or reconfigure software systems using the three approaches considered here
with high probability for all inputs. Taken together, the above
constitutes the first proof 
that {\em no} currently-used method (including search-based methods based on
evolutionary algorithms (see \cite[Section 5]{HMZ12} and references)
can guarantee both efficient and correct operation for all inputs
for these problems.

As described in Section \ref{SectTCM}, efficient correctness-guaranteed methods
may yet exist relative to plausible restrictions on the input and output.
It seems reasonable to conjecture that some restrictions 
relative to the parameters listed in Table \ref{TabPrm} should render 
these problems tractable. However, almost none of these restrictions or
indeed many possible combinations of these restrictions can yield
tractability, even when the parameters involved are restricted to very
small constants (Results B--G). We do have some initial fp-tractability results
(Results H and I). Taken together, our fp-results paint a disconcerting picture
for problems SDes-Spec, SDes-CompA, SRec-Spec, and SRec-CompA, as they
suggest that making both the software systems and the degree of allowable 
adaptation 
small under the approaches encoded in these problems does not yield 
tractability. However, the situation for problems SDes-Comp and SRec-Comp
may not be so dire.  To date, we have not been able to prove fp-intractability 
relative to a number of the individual parameters and parameter-combinations 
considered here for these problems. Hence, if fp-tractability holds in at least 
some of those cases, this would constitute proof that component selection 
without adaptation is tractable in a wider set of circumstances than either 
{\em de novo} design or component selection with adaptation. 

Two valid objections to our fp-tractability results are that (1) the
algorithms underlying these results are crude and rely on brute-force search
and (2) the running times of these algorithms are (to be blunt,
ludicrously) impractical. These objections are often true of the initial
fp-algorithms derived relative to a parameter-set. However, 
once fp-tractability is proven, surprisingly effective 
fp-algorithms are often subsequently developed with 
greatly diminished non-polynomial terms and polynomial terms that are quadratic
or even linear in the input size (see \cite{CF+15,DF13} and references). 

A final very important proviso is in order -- namely, as illuminating as
the results given here are in demonstrating basic forms of (in)tractability
for software design and reconfiguration problems relative to the three
approaches considered, these results do not necessarily imply that methods
currently being applied to design or reconfigure software are impractical.
Differing software and component models, the particular situations in which 
these currently-used methods are 
being applied, and accepted standards by which method practicality is assessed 
may render the results given here irrelevant. For example, current methods may 
already be implicitly exploiting restrictions on the input and output such that
both efficient and correct operation (or operation that is correct with
probability very close to one) are guaranteed.
That being said, not knowing the precise conditions under which
such practicality holds could have serious consequences, {\em e.g.},
drastically slowed software creation time and/or unreliable software operation, 
if these conditions are violated. These consequences would be particularly
damaging in the case of runtime-based applications like ubiquitous and
autonomic computing. Given that reliable software operation is very important 
and efficient software design and reconfiguration is at the very least
desirable, the acquisition of such knowledge via a combination of rigorous 
empirical and theoretical analyses should be a priority. With respect to 
theoretical analyses, it is our hope that the techniques and results in this 
paper comprise a useful first step.

\section{Conclusions}\label{SectConc}

We have presented a formal characterization of the problems of software
system design and reconfiguration by {\em de novo} design, component selection,
and component selection with adaptation. Our complexity analyses reveal that,
while these problems are computationally intractable in general, there are
restrictions that render them tractable. Though the immediate practical
utility of our tractability results is questionable given the basic models
of software requirements, software systems and components relative to
which they were derived, our intractability results give the first
rigorous computational comparison between the three approaches to software
design considered here. In particular, our results as a whole establish that all
three approaches are equally
computationally difficult in general but suggest that software creation
by component selection may be tractable under more circumstances than the
other two approaches.

There are several possible directions for future research. 
The first is to complete the analysis begun here 
to see if software creation by component selection
really is fp-tractable for software systems that are small and/or 
created with small amounts of adaptation. The second is to extend this analysis to
the more realistic models of software requirements, software systems, 
components, and component libraries sketched in Section
\ref{SectGenRes}. Last but certainly not least, derived tractability
results should be implemented and tested in designing and reconfiguring
actual software systems. Such testing will give invaluable guidance in
phrasing future theoretical analyses along the lines sketched here; in turn,
such analyses will hopefully help to guide
future research in comp-onent-based software development.

\newpage

\section{Acknowledgments}

The authors extend most grateful thanks to Iris van Rooij and Maria
Otworowska (Donders Institute for Brain, Cognition, and Behaviour, Radboud
University Nijmegen) with whom they collaborated on the formalization 
of the adaptive toolbox theory of human decision-making that underlies
the formalizations of component-based design and reconfiguration 
analyzed here. They would also like to thank the three reviewers for
comments that helped greatly to improve the presentation of this paper.
TW was supported by NSERC Discovery Grants RGPIN 228104-2010 
and 228104-2015.



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{abbrv}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,paper}
\bibliography{paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
%\begin{thebibliography}{1}
%
%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.

\appendix

\section{Proofs of Selected Results}

\label{AppProof}

All of our intractability results will be derived using reductions from the
following $NP$-hard problem:

\noindent
{\sc Dominating set} \cite[Problem GT2]{GJ79} \\
{\em Input}: An undirected graph $G = (V, E)$ and an integer $k$. \\
{\em Question}: Does $G$ contain a dominating set of size $\leq k$, {\em i.e.}, is
              there a subset $V' \subseteq V$, $|V'| \geq k$, such that for
	      all $v \in V'$, either $v \in V'$ or there is a $v' \in V'$ such
	      that $(v, v') \in E$?

\noindent 
For each vertex $v \in V$, let the complete neighbourhood $N_C(v)$ of $v$ be the
set composed of $v$ and the set of all vertices in $G$ that are adjacent to $v$ 
by a single edge, {\em i.e.}, $v \cup \{ u ~ | ~ u ~ \in V ~ \rm{and} ~ (u,v) \in E\}$.
We assume below an arbitrary ordering
on the vertices of $V$ such that $V = \{v_1, v_2, \ldots, v_{|V|}\}$.

\vspace*{-0.1in}

\begin{lemma}
{\sc Dominating Set} polynomial-time many-one reduces to SDes-Spec such that in
the constructed instance of SDes-Spec, $|A| = 2$, $|sel| = 0$,  and $|prc|$ is
a function of $k$ in the given instance of {\sc Dominating Set}.
%
\label{LemRedSDesSpec}
\end{lemma}

\begin{proof}
Given an instance $\langle G = (V, E), k\rangle$ of {\sc Dominating 
set}, the constructed instance $\langle I, A, R, X = 
\langle |sel|,|prc|\rangle \rangle$ of SDes-Spec has $I = \{i_1, i_2,
\ldots i_{|V|}\}$, $A = \{0, 1\}$, $|sel| = 0$, and $|prc| = k$. There
are $|V| + 1$ situation-action pairs in $R$ such that (1) for $r_i = 
(s_i, a_i)$, $1 \leq i \leq |V|$, $v(i_j) = True$ if $v_j \in N_C(v_i)$
and is $False$ otherwise and $a_i = 1$, and (2) for $r_{|V|+1} =
(s_{|V|+1}, a_{|V|+1})$, all $v(i_j)$ are $False$ and $a_{|V|+1} = 0$.
Note that the instance of SDes-Spec described above can be constructed in 
time polynomial in the size of the given instance of {\sc Dominating set}. 

If there is a dominating set of size at most $k$ in the given instance of
{\sc Dominating set}, construct a software system consisting of a 
default \texttt{*}-condition selector and a single
procedure in which the $k$ \texttt{IF-THEN} statements have 
situation-variable conditions corresponding to the vertices in the dominating 
set (adding arbitrary other vertex situation-variables if the size of the
dominating set is less than $k$) and action $1$ and the final 
\texttt{ELSE} statement has action $0$. Observe that this
software system satisfies all situation-action pairs in $R$ and has
$|sel| = 0$ and $|prc| = k$. 

Conversely, suppose that the constructed instance 
of SDes-Spec has a software system satisfying $R$ with $|sel| = 0$  and
$|prc| \leq k$. The selector in this system must be the default selector
as it is the only selector with $|sel| = 0$. As for the
single procedure attached to that selector, it has two possible
structures:

\begin{enumerate}
\item{
\textit{No negated situation-variable conditions}: As $r_{|V|+1}$ has
no situation-variables set to $True$, it can only be processed correctly
by the final \texttt{ELSE}-statement, which must thus execute 
action $0$. In order to accept all other situation-pairs in $R$,
the $k$ conditions must then have situation-variables
whose corresponding vertices form a dominating set in $G$
of size at most $k$.
}
\item{
\textit{Negated situation-variables are present}: 
Let $c$ be the first
negated situation-variable condition encountered moving down the
code in the procedure, $C$ be the set of unnegated situation-variable
conditions encountered before $c$, and $R' \subseteq R$ be the set of
situation-action pairs not recognized by the situation-variables in $C$.
As $|prc| \leq k$, $|C| \leq k - 1$. Moreover, as
situation-action pair $r_{|V|+1}$ has no 
situation-variable with value $True$ and hence cannot be recognized
by an \texttt{IF-THEN} statement with an unnegated situation-variable
condition, $r_{|V|+1} \in R'$. 

Let $R'' \subset R$ be
such that $R' = R'' \cup \{r_{|V|+1}\}$. If $R''$ is empty, then the 
variables in $C$ must have recognized all situation-action pairs in
$R$ except $r_{|V|+1}$, and hence the vertices corresponding to the
situation-variables in $C$ form a dominating set in $G$ of size at
most $k - 1$. If $R''$ is not empty, situation-variable $c$ cannot 
have value $False$ for any of the situation-action pairs in $R''$
because having either $0$ or $1$ as the action executed by the 
associated \texttt{IF-THEN} statement would result in the procedure executing 
the wrong action for at least one situation-action pair in $R'$ (if $0$, at least
one of the situation-action pairs in $R''$; if $1$, $r_{|V|+1}$). However,
this implies that all situation-action pairs in $R''$ have value $True$
for $c$, which in turn implies that the vertices corresponding to
the situation-variables in $C \cup \{c\}$ form a dominating set in $G$ of size at
most $k$.
}
\end{enumerate}

\noindent
Hence, the existence of a satisfying software system for the
constructed instance of SDes-Spec implies the existence of a
dominating set of size at most $k$ for the given instance  of
{\sc Dominating Set}.

To complete the proof, note that in the constructed instance of SDes-Spec,
$|A| = 2$, $|sel| = 1$, and $|prc| = k$.
\end{proof}

% \newpage

%\begin{lemma}
%{\sc Dominating Set} polynomial-time many-one reduces to SDes-CompA such that 
%in the constructed instance of SDes-CompA, $|A| = d = 2$, $|sel| = 0$, 
%$|L_{sel}| = L_{prc}| = 1$, and $|prc|$ and $c_c$ are functions of $k$ in 
%the given instance of {\sc Dominating Set}.
%%
%\label{LemRedSDesCompA} 
%\end{lemma} 
%
%\begin{proof}[(sketch)] 
%Given an instance $\langle G = (V, E),$ $k\rangle$ of {\sc Dominating set}, 
%the constructed instance $\langle I, A, R,$ $L_{sel},$ $L_{prc}, d, 
%c_c \rangle$
%of SDes-CompA has $I$, $A$, and $R$ as in the reduction in Lemma 
%\ref{LemRedSDesSpec} above. Let $L_{sel}$ consist of the default selector and 
%$L_{prc}$ consist of a single procedure whose $k$ \texttt{IF-THEN} statements 
%have conditions that are arbitrarily-selected situation-variables in $I$ and 
%execute action $1$ and whose \texttt{ELSE} statement executes action $0$. 
%Finally, set $d = 2$ and $c_c = k$.
%Note that the instance of SDes-Spec described above can be constructed in 
%time polynomial in the size of the given instance of {\sc Dominating set}. 
%The proof of correctness is a modification of that given for the reduction
%in Lemma \ref{LemRedSDesSpec}.
%To complete the proof, note that in the constructed instance of SDes-CompA,
%$|A| = 2$, $|sel| = 0$, $|L_{sel}| = |L_{prc}| = 1$, and $|prc| = c_c = k$.
%\end{proof}

\begin{lemma}
{\sc Dominating Set} polynomial-time many-one reduces to SDes-Comp such that 
in the constructed instance of SDes-CompA, $|A| = 2$, $|L_{sel}| = 1$,
and $d$ is a function of $k$ in the given instance of {\sc Dominating Set}.
%
\label{LemRedSDesComp} 
\end{lemma} 

\begin{proof}
Given an instance $\langle G = (V, E), k\rangle$ of {\sc Dominating 
set}, the constructed instance $\langle I, A, R, L_{sel}, L_{prc},
d\rangle$ of SDes-Comp has $I = \{i_1, i_2,
\ldots i_{2|V|}\}$ and $A = \{0, 1\}$. There
are $|V| + 1$ situation-action pairs in $R$ such that 
(1) for $r_i = 
(s_i, a_i)$, $1 \leq i \leq |V|$, $v(i_i) = True$, $v(i_{|V| + j}) = True$ 
if $v_j \in N_C(v_i)$, all other $v(i_j)$ are $False$,
and $a_i = 1$, and (2) for $r_{|V|+1} =
(s_{|V|+1}, a_{|V|+1})$, all $v(i_j) = False$ and $a_{|V|+1} = 0$.
There is a single selector in $L_{sel}$ whose $|V| - 1$ \texttt{IF-THEN}
statement conditions are the first $|V| - 1$ situation-variables in $I$.
There are $|V|$ procedures in $L_{prc}$ such that procedure $i$,
$1 \leq i \leq |V|$, has an \texttt{IF-THEN} statement for each of the
vertices in $N_C(v_i)$ whose condition is the situation-variable associated with
that vertex and which executes action $1$ and an \texttt{ELSE} statement that
executes action $0$. Finally, let $d = k + 1$.
Note that the instance of SDes-Comp described above can be constructed in 
time polynomial in the size of the given instance of {\sc Dominating set}. 

If there is a dominating set of size at most $k$ in the given instance
of {\sc Dominating Set}, construct a software system consisting of the 
single selector in $L_{sel}$ and the at most $k$ procedures from
$L_{prc}$ corresponding to the vertices in the dominating set. For each
of the $|V| - 1$ \texttt{IF-THEN} statements in the selector, call the
procedure encoding the neighbourhood of the vertex in the dominating
set which dominates the vertex corresponding to the situation-variable
in that statement's condition. For the \texttt{ELSE} statement in the
selector, execute the procedure encoding the neighbourhood of the
vertex in the dominating set that dominates vertex $v_{|V|}$.
Observe that this software system satisfies all situation-action pairs in 
$R$ and has $d = k + 1$. 

Conversely, suppose that the constructed instance 
SDes-Comp has a software system constructed from at most $d = k + 1$
distinct components from $L_{sel}$ and $L_{prc}$ that satisfies all
of the situation-action pairs in $R$. As the selector is constructed 
such that each of the first $|V|$ situation-action pairs in $R$ has
its own associated procedure and each procedure accepts the vertices in
a specific vertex-neighbourhood in $G$, in order for these situation-action 
pairs to be satisfied, the distinct procedures in the software system
must correspond to a dominating set for $G$ (note that both $r_{|V|}$ and
 $r_{|V|+1}$ are satisfied by the procedure associated with the 
\texttt{ELSE} statement in the selector). As $d = k + 1$ and the
system had to incorporate a selector from $L_{sel}$, this means that
there are at most $k$ such procedures and hence a dominating set
of size at most $k$ in the given instance of {\sc Dominating Set}.

To complete the proof, note that in the constructed instance of SDes-Comp,
$|A| = 2$, $|L_{sel}| = 1$, and $d = k + 1$.
\end{proof}

\noindent
{\bf Result A}: {\em SDes-Spec and SDes-Comp
                    are $NP$-hard.}

\begin{proof}
Follows from the $NP$-hardness of {\sc Dominating Set} and the reductions in
Lemmas \ref{LemRedSDesSpec} and \ref{LemRedSDesComp},
respectively.
\end{proof}

\noindent
{\bf Result B}: 
{\em SDes-Spec is $W[2]$-hard for $\{ |A|, |sel|, |prc|\}$ when 
      $|A| = 2$ and $|sel| = 0$.}

\begin{proof}
Follows from the $W[2]$-hardness of $\{ k \}$-{\sc Dominat-ing Set}
\cite{DF13} and the reductions from {\sc Dominating Set} to SDes-Spec
given in Lemma \ref{LemRedSDesSpec}.
\end{proof}

%\noindent
%{\bf Result C}:
%{\em SDes-CompA is $W[2]$-hard for $\{ |A|, |sel|, |prc|, d,$ $|L_{sel}|, 
%      |L_{prc}|, c_c\}$ when $|A| = d = 2$, $|sel| = 0$ and $|L_{sel}| = 
%      |L_{prc}| = 1$.}
%
%\begin{proof}
%Follows from the $W[2]$-hardness of $\{ k \}$-{\sc Dominat-ing Set}
%\cite{DF13} and the reductions from {\sc Dominating Set} to SDes-CompA
%given in Lemma \ref{LemRedSDesCompA}.
%\end{proof}
%
%\noindent
%{\bf Result D}:
%{\em SDes-CompA is $W[2]$-hard for $\{ |A|, d, |L_{sel}|\}$
%      when $|A| = 2$ and $|L_{sel}| = 1$.}
%
%\begin{proof}
%Follows from the $W[2]$-hardness of $\{ k \}$-{\sc Dominat-ing Set}
%\cite{DF13} and the reductions from {\sc Dominating Set} to SDes-Comp
%given in Lemma \ref{LemRedSDesComp}.
%\end{proof}

%\noindent
%{\bf Result H}: 
%{\em SDes-Spec, SDes-CompA, SDes-Comp, SRec-Spec, SRec-CompA, and SRec-Comp 
%      are fp-tractable for $\{ |I| \}$.}
%
%\begin{proof}[(sketch)] 
%All six problems can be solved by first generating all
%possible two-level software systems 
%that are based on $|I|$ situation-variables and $|A|$ actions and then 
%checking each generated system for required problem-specific properties, 
%{\em e.g.}, at most $c_l$ component-changes were made in transforming $S$ into
%$S'$ (SRec-CompA, SRec-Comp). All systems can be generated in time that is
%upper-bounded by a function of $|I|$ and all checks can be done in time that
%is either polynomial in the input size or upper-bounded by a function of $|I|$.
%\end{proof}

% that's all folks
\end{document}
