input-output examples [47, 48]. Analyses of these problems may also give
insights into the more general problem of program synthesis [49, 50, 51]. The
third research direction involves not so much emergent software systems but
self-adaptive and component-based software systems in general. Invoking the
terminology in the taxonomy of component models given in [52], emergent
software systems have operation-based interfaces, provide horizontal and
partial vertical component binding during composition, and explicitly
distinguish between the required and provided interfaces of a component. These
characteristics are not only exploited by our intractability result reductions
but are also typical of many other component models [52, Table 2]. Hence, it
would be of great interest to see if our analyses for emergent software
systems could be extended to software system creation and adaptation problems
arising relative to other proposed types of self-adaptive software systems [1,
7, 8] and within component-based software engineering in general [53, 54, 55].

## Acknowledgements

The authors thank Barry Porter for invaluable discussions about and comments
on previous versions of this paper; though we have not been able to address
all of his concerns, we very much appreciate his efforts in helping us create
a better and more relevant paper. TW would also like to thank Antonina
Kolokolova for useful discussions on Rice’s Theorem and Ulrike Stege for
introducing him to the research area of self-adaptive software systems. TW was
supported by National Science and Engineering Council (NSERC) Discovery Grant
228104-2015.

## References

  * [1] B. H. Cheng, R. de Lemos, H. Giese, P. Inverardi, J. Magee, J. Andersson, B. Becker, N. Bencomo, Y. Brun, B. Cukic _et al._ , “Software engineering for self-adaptive systems: A research roadmap,” in _Software Engineering for Self-adaptive Systems_ , ser. Lecture Notes in Computer Science. Springer, 2009, vol. 5525, pp. 1–26.
  * [2] C. Krupitzer, F. M. Roth, S. VanSyckel, G. Schiele, and C. Becker, “A survey on engineering approaches for self-adaptive systems,” _Pervasive and Mobile Computing_ , vol. 17, pp. 184–206, 2015.
  * [3] M. Salehie and L. Tahvildari, “Self-adaptive software: Landscape and research challenges,” _ACM Transactions on Autonomous and Adaptive Systems (TAAS)_ , vol. 4, no. 2, p. 14, 2009.
  * [4] D. G. D. L. Iglesia and D. Weyns, “MAPE-K formal templates to rigorously design behaviors for self-adaptive systems,” _ACM Transactions on Autonomous and Adaptive Systems (TAAS)_ , vol. 10, no. 3, pp. 1–31, 2015.
  * [5] K. Angelopoulos, A. V. Papadopoulos, V. E. S. Souza, and J. Mylopoulos, “Engineering self-adaptive software systems: From requirements to model predictive control,” _ACM Transactions on Autonomous and Adaptive Systems (TAAS)_ , vol. 13, no. 1, pp. 1–27, 2018.
  * [6] A. Filieri, M. Maggio, K. Angelopoulos, N. D’ippolito, I. Gerostathopoulos, A. B. Hempel, H. Hoffmann, P. Jamshidi, E. Kalyvianaki, C. Klein _et al._ , “Control strategies for self-adaptive software systems,” _ACM Transactions on Autonomous and Adaptive Systems (TAAS)_ , vol. 11, no. 4, pp. 1–31, 2017.
  * [7] R. De Lemos, D. Garlan, C. Ghezzi, H. Giese, J. Andersson, M. Litoiu, B. Schmerl, D. Weyns, L. Baresi, N. Bencomo _et al._ , “Software engineering for self-adaptive systems: Research challenges in the provision of assurances,” in _Software Engineering for Self-Adaptive Systems III_ , ser. Lecture Notes in Computer Science. Springer, 2017, vol. 9640, pp. 3–30.
  * [8] R. De Lemos, H. Giese, H. A. Müller, M. Shaw, J. Andersson, M. Litoiu, B. Schmerl, G. Tamura, N. M. Villegas, T. Vogel _et al._ , “Software engineering for self-adaptive systems: A second research roadmap,” in _Software Engineering for Self-Adaptive Systems II_ , ser. Lecture Notes in Computer Science. Springer, 2013, vol. 7475, pp. 1–32.
  * [9] R. G. Downey and M. R. Fellows, _Fundamentals of Parameterized Complexity_. Berlin: Springer, 2013.
  * [10] M. R. Garey and D. S. Johnson, _Computers and Intractability_. W.H. Freeman, 1979.
  * [11] O. Goldreich, _Computational Complexity: A Conceptual Perspective_. Cambridge University Press, 2008.
  * [12] R. R. Filho and B. Porter, “Defining emergent software using continuous self-assembly, perception, and learning,” _ACM Transactions on Autonomous and Adaptive Systems (TAAS)_ , vol. 12, no. 3, pp. 16:1–16:25, 2017\.
  * [13] B. Porter, M. Grieves, R. R. Filho, and D. Leslie, “${RE^{X}}$: A development platform and online learning approach for runtime emergent software systems,” in _12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)_ , 2016, pp. 333–348.
  * [14] R. R. Filho, B. Porter, F. Costa, and M. Pereira de Sá, “Towards emergent microservices for client-tailored design,” in _Proceedings of the 19th Workshop on Adaptive and Reflexive Middleware_. ACM, 2018, pp. 1–6.
  * [15] B. Porter and R. R. Filho, “Distributed emergent software: Assembling, perceiving and learning systems at scale,” in _Proceedings of the 13th IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO)_. IEEE, 2019.
  * [16] E. H. Page and J. M. Opper, “Observations on the complexity of composable simulation,” in _Proceedings of the 31st Winter Conference on Simulation_ , vol. 1. ACM, 1999, pp. 553–560.
  * [17] M. Petty, E. Weisel, and R. Mielke, “Computational complexity of selecting components for composition,” in _Proceedings of the Fall 2003 Simulation Interoperability Workshop_ , 2003, pp. 14–19.
  * [18] R. G. Bartholet, D. C. Brogan, and P. F. Reynolds Jr, “The computational complexity of component selection in simulation reuse,” in _Proceedings of the 2005 Winter Simulation Conference_ , 2005, pp. 2472–2481.
  * [19] M. Nouri and J. Habibi, “Approximating component selection with general costs,” in _Advances in Computer Science and Engineering_. Springer, 2008, pp. 61–68.
  * [20] M. R. Fox, D. C. Brogan, and P. F. Reynolds Jr, “Approximating component selection,” in _Proceedings of the 36th conference on Winter simulation_. Winter Simulation Conference, 2004, pp. 429–434.
  * [21] N. Haghpanah, S. Moaven, J. Habibi, M. Kargar, and S. H. Yeganeh, “Approximation algorithms for software component selection problem,” in _Proceedings of the 14th Asia-Pacific Software Engineering Conference (APSEC 2007)_. IEEE, 2007, pp. 159–166.
  * [22] T. Wareham and M. Sweers, “On the computational complexity of designing and reconfiguring component-based software systems,” in _Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communication Technologies (BICT 2015)_. Brussels: Institute for Computer Sciences, Social-informatics, and Telecommunications Engineering (ICST), 2015, pp. 425–432.
  * [23] ——, “On the computational complexity of designing and reconfiguring component-based software systems,” _EAI Endorsed Transactions on Self-Adaptive Systems_ , vol. 16, no. 5, p. e4, 2016.
  * [24] ——, “On the computational complexity of designing and reconfiguring component-based software systems: A computational complexity approach (full version),” 2022, coRR abs/2205.05001 (38 pages). [Online]. Available: https://arxiv.org/abs/2205.05001
  * [25] L. A. Hemaspaandra and R. Williams, “Complexity Theory Column 76: An atypical survey of typical-case heuristic algorithms,” _ACM SIGACT News_ , vol. 43, no. 4, pp. 70–89, 2012.
  * [26] R. Motwani and P. Raghavan, _Randomized Algorithms_. Chapman & Hall/CRC, 2010.
  * [27] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, _Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties_. Springer, 1999.
  * [28] L. Fortnow, “The Status of the P Versus NP Problem,” _Communications of the ACM_ , vol. 52, no. 9, pp. 78–86, 2009.
  * [29] A. M. Turing, “On computable numbers, with an application to the entscheidungsproblem,” _Proceedings of the London Mathematical Society_ , vol. 42, no. 230-265, 1936.
  * [30] B. Porter, “Runtime modularity in complex structures: A component model for fine grained runtime adaptation,” in _Proceedings of the 17th International ACM SIGSOFT Symposium on Component-based Software Engineering_. ACM, 2014, pp. 29–34.
  * [31] A. Wigderson, “P, NP and mathematics — A computational complexity perspective,” in _Proceedings of ICM 2006: Volume I_. Zurich: EMS Publishing House, 2007, pp. 665–712.
  * [32] R. G. Downey and M. R. Fellows, _Parameterized Complexity_. Berlin: Springer, 1999.
  * [33] I. van Rooij, M. Blokpoel, J. Kwisthout, and T. Wareham, _Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis_. Cambridge, UK: Cambridge University Press, 2019.
  * [34] J. E. Hopcroft, R. Motwani, and J. Ullman, _Introduction to Automata Theory, Languages, and Computation_ , 2nd ed. Addison-Wesley, 2001.
  * [35] T. Wareham, “Systematic parameterized complexity analysis in computational phonology,” Ph.D. dissertation, University of Victoria, Canada, 1999.
  * [36] C. Lund and M. Yannakakis, “On the hardness of approximating minimization problems,” _Journal of the ACM (JACM)_ , vol. 41, no. 5, pp. 960–981, 1994\.
  * [37] M. Cadoli, F. M. Donini, P. Liberatore, and M. Schaerf, “Preprocessing of intractable problems,” _Information and Computation_ , vol. 176, no. 2, pp. 89–120, 2002.
  * [38] J. L. Balcázar, J. Díaz, and J. Gabarró, _Structural Complexity I_ , ser. EATCS Monographs on Theoretical Computer Science. Berlin: Springer-Verlag, 1988, vol. 11.
  * [39] B. Rossman, R. A. Servedio, and L.-Y. Tan, “An average-case depth hierarchy theorem for boolean circuits,” in _56th Annual IEEE Symposium on Foundations of Computer Science (FOCS)_. IEEE, 2015, pp. 1030–1048.
  * [40] J. L. Balcázar, J. Díaz, and J. Gabarró, _Structural Complexity II_ , ser. EATCS Monographs on Theoretical Computer Science. Berlin: Springer-Verlag, 1990, vol. 22.
  * [41] S. Aaronson. (2020) The complexity zoo. [Online]. Available: https://complexityzoo.uwaterloo.ca/Complexity_Zoo
  * [42] D. S. Johnson, “A catalog of complexity classes,” in _Handbook of Theoretical Computer Science_ , J. van Leeuwen, Ed. Elsevier, 1990, vol. A: Algorithms and complexity, pp. 67–161.
  * [43] L. Gyongyosi and S. Imre, “A survey on quantum computing technology,” _Computer Science Review_ , vol. 31, pp. 51–71, 2019.
  * [44] E. Bernstein and U. Vazirani, “Quantum complexity theory,” _SIAM Journal on Computing_ , vol. 26, no. 5, pp. 1411–1473, 1997.
  * [45] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, _Parameterized Algorithms_. Springer, 2015.
  * [46] F. V. Fomin, D. Lokshantov, S. Saurabh, and M. Zehavi, _Kernalization: Theory of Parameterized Prepreocessing_. Cambridge, UK: Cambridge University Press, 2019.
  * [47] R. R. Filho, A. Wild, and B. Porter, “Code synthesis in self-improving software systems,” in _4th International Workshop on Foundations and Applications of Self* Systems (FAS* W)_. IEEE, 2019, pp. 4–5.
  * [48] C. McGowan, A. Wild, and B. Porter, “Experiments in genetic divergence for emergent systems,” in _Proceedings of the 4th International Workshop on Genetic Improvement_ , 2018, pp. 9–16.
  * [49] M. Balog, A. L. Gaunt, M. Brockschmidt, S. Nowozin, and D. Tarlow, “Deepcoder: Learning to write programs,” in _5th International Conference on Learning Representations, ICLR 2017-Conference Track Proceedings_ , 2017.
  * [50] S. Gulwani, “Dimensions in program synthesis,” in _Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming_ , 2010, pp. 13–24.
  * [51] S. Gulwani, O. Polozov, and R. Singh, “Program synthesis,” _Foundations and Trends® in Programming Languages_ , vol. 4, no. 1-2, pp. 1–119, 2017.
  * [52] I. Crnkovic, S. Sentilles, A. Vulgarakis, and M. R. Chaudron, “A classification framework for software component models,” _IEEE Transactions on Software Engineering_ , vol. 37, no. 5, pp. 593–615, 2011.
  * [53] D. Gruntz, S. Murer, and C. Szyperski, _Component Software-Beyond Object-Oriented Programming_. Addison-Wesley, 2002.
  * [54] G. T. Heineman and W. T. Councill, Eds., _Component-Based Software Engineering: Putting the Pieces Together_. Addison-Wesley, 2000.
  * [55] T. Vale, I. Crnkovic, E. S. de Almeida, P. A. d. M. S. Neto, Y. C. Cavalcanti, and S. R. de Lemos Meira, “Twenty-eight years of component-based software engineering,” _Journal of Systems and Software_ , vol. 111, pp. 128–148, 2016.
  * [56] R. Karp and R. J. Lipton, “Turing machines that take advice,” _Enseignement Mathematique._ , vol. 28, pp. 191–209, 1982.

##  Appendix A Proofs of Selected Results

Let us first prove Result A.9. In the reduction below, instead of encoding a
dominating set of size $k$ implicitly in the components implementing
procedures InSet1(), InSet2(), …, InSetk() as in the reductions in the proofs
of Lemmas 4 and 5, a candidate dominating set is encoded explicitly in binary-
valued vector vS in component Base in the components used to implement the
procedures vertexStatus1(), vertexStatus2(), …, vertexStatus(|V|(). Moreover,
checks to see if this candidate is an actual dominating set of size $k$ in $G$
are explicitly coded in component Base (see Figure 7. This allows us to reduce
the maximum number of interfaces provided by any component and the maximum
number of components implemented by any interface to 1 and 2, respectively,
while maintaining a maximum component depth of 3.

Figure 7: General structure of valid software systems created by the reduction
in the proof of Result A.9. Note that index $x$ in DomSetStatusx is such that
$x\in\\{0,1\\}$. Following the convention in Figure 3, interfaces with
multiple implementing components are enclosed in dashed boxes.

Result A.9

For any choice of $Rew()$ and $Env()$, if $\langle
I_{ci},C_{pi},S_{depth}\rangle$-ESCreatepoly is fp-tractable then $P=NP$.

Proof: Consider the following polynomial-time Karp reduction from Dominating
set to CSCreatepoly: given an instance $I=\langle G=(V,E),k\rangle$ of
Dominating set, construct an instance $I^{\prime}=\langle
R,L_{int},L_{comp},c\rangle$ of CSCreatepoly in which $R$ is the same as that
given in the reduction in the proof of Lemma 4. Let $L_{int}$ consist of
$|V|+2$ interfaces broken into three groups:

  1. 1.

A single interface of the form

            interface base {
             void main(Input I)
        }

  2. 2.

A set of $|V|$ interfaces of the form

            interface vertStatJ {
             int vertexStatusJ()
        }

for $1\leq{\tt J}\leq|V|$.

  3. 3.

An interface of the form

            interface domSetStat {
             int domSetStatus()
        }

Let $L_{comp}$ consist of $|V|+3$ components broken into three groups:

  1. 1.

A single component of the form

            component Base provides base
                       requires vertStat1, vertStat2, ...,
                                vertStat|V| {
             void main(Input I) {

                 create integer array vS of length |V|

                 vS[1] = vertexStatus1()
                 vS[2] = vertexStatus2()
                     ...
                 vS[|V|] = vertexStatus|V|()

                 numFound = 0
                 for i = 1 to |V| do
                     if vS[j] == 1 then
                           numFound = numFound + 1
                 if numFound == k then
                     isCandidatekDomSet = True
                 else
                     isCandidatekDomSet = False

                 if isCandidatekDomSet then
                     numFound = 0
                     for i = 1 to |V| do
                         if v_I(x_i) and vS[i] == 1 then
                             numFound = numFound + 1

                     if numFound > 0 then
                         output 1
                     else
                         output 0
                  else
                     output 0
             }
        }

  2. 2.

A set of $|V|$ components of the form

            component VertexStatusJ provides vertStatJ {
                              requires domSetStat
             int vertexStatusJ() {
                 return domSetStatus()
             }
        }

for $1\leq{\tt J}\leq|V|$.

  3. 3.

Two components of the form

            component DomSetStatus0 provides domSetStat {
             int domSetStatus() {
                 return 0
             }
        }

        component DomSetStatus1 provides domSetStat {
             int domSetStatus() {
                 return 1
             }
        }

Observe that in component Base, if entry $i$ of array vS has value $1$, then
vertex $i$ is in the candidate dominating set for $G$ encoded in vS. Finally,
let $c$ be component Base in $L_{comp}$. Note that the instance of
CSCreatepoly described above can be constructed in time polynomial in the size
of the given instance of Dominating set; moreover, as there is only a
$|V|$-length assignment statement block and two single-level loops in the
component code that each execute at most $|V|<|I|$ times, any component-based
software system created relative to $L_{int}$, $L_{comp}$, and $c$ runs in
time linear in the size of input $I^{\prime}$.

Let us now verify the correctness of this reduction:

  * •

Suppose there is a dominating set $D$ of size at most $k$ in the given
instance of Dominating set; if $|D|<k$, augment $D$ with $k-|D|$ arbitrary
other vertices from $G$ such that $|D|=k$. Construct a component-based
software system consisting of $c$ and all $|V|$ components VertexStatusJ for
$1\leq{\tt J}\leq|V|$ in which the domSetStat interface in component
VertexStatusJ is implemented by component DomSetStatus1 if vertex J is in $D$
and by component DomSetStatus0 otherwise. Observe that for each
$(i_{j},o_{j})\in R$, this software system produces output $o_{j}$ given input
$i_{j}$.

  * •

Conversely, suppose that the constructed instance of CSCreatepoly has a
working component-based software system based on $c$ relative to $L_{int}$,
$L_{comp}$, and $R$. In order to accommodate all input-output pairs in $R$,
the $|V|$ vertexStatus components must implement their domSetStat interfaces
such that the $1$-values in array vS specify a dominating set of size $k$ in
$G$. Hence, the existence of a working component-based software system for the
constructed instance of CSCreatepoly implies the existence of a dominating set
of size $k$ for the given instance of Dominating set.

The reduction above is thus correct. Given the $NP$-hardness of Dominating
set, this reduction implies that CSCreatepoly is $NP$-hard when $I_{ci}=2$,
$C_{pi}=1$, and $S_{depth}=3$ and hence by Lemma 3 not fp-tractable relative
to these parameters unless $P=NP$. The fp-intractability result for
ESCreatepoly then follows by contradiction from Observation 1.

Figure 8: General structure of valid software systems created by the reduction
in the proof of Result A.10. Note that index $x$ in DomSetStatusx is such that
$x\in\\{0,1\\}$. Following the convention in Figure 3, interfaces with
multiple implementing components are enclosed in dashed boxes.

Let us now prove Result A.10. In the reduction below, we modify the reduction
in the proof of Result A.9 to split the call to procedures vertexStatus1(),
vertexStatus2(), …, vertexStatus|V|() in component Base over $|V|$ base-
components (see Figured 8). This still allows us to have the values of the
maximum number of interfaces provided by any component and the maximum number
of components implemented by any interface as 1 and 2, respectively, as in the
previous reduction but trades off constant-valued component depth for a
constant-valued maximum number of interfaces required by any component.

Result A.10

For any choice of $Rew()$ and $Env()$, if $\langle
I_{ci},C_{pi},C_{ri}\rangle$-ESCreatepoly is fp-tractable then $P=NP$.

Proof: Consider the following polynomial-time Karp reduction from Dominating
set to CSCreatepoly: given an instance $I=\langle G=(V,E),k\rangle$ of
Dominating set, construct an instance $I^{\prime}=\langle
R,L_{int},L_{comp},c\rangle$ of CSCreatepoly in which $R$ is the same as that
given in the reduction in the proof of Lemma 4. Let $L_{int}$ consist of
$2|V|+1$ interfaces broken into four groups:

  1. 1.

A single interface of the form

            interface base {
             void main(Input I)
        }

  2. 2.

A set of $|V|-1$ interfaces of the form

            interface baseJ {
             void callBaseJ(Input I, int[] vS)
        }

for $2\leq{\tt J}\leq|V|$.

  3. 3.

A set of $|V|$ interfaces of the form

            interface vertStatJ {
             int vertexStatusJ()
        }

for $1\leq{\tt J}\leq|V|$.

  4. 4.

An interface of the form

            interface domSetStat {
             int domSetStatus()
        }

Let $L_{comp}$ consist of $2|V|+2$ components broken into five groups:

  1. 1.

A single component of the form

            component Base provides base
                       requires vertStat1, base2 {
             void main(Input I) {

                 create integer array vS of length |V|

                 vS[1] = vertexStatus1()

                 callBase2(I, vS)
             }
        }

  2. 2.

A set of $|V|-2$ components of the form

            component BaseJ provides baseJ
                       requires vertStatJ, base(J + 1) {
             void callBaseJ(Input I, int[] vS) {

                 vS[J] = vertexStatusJ()

                 callBase(J + 1)(I, vS)
             }
        }

for $2\leq{\tt J}\leq|V|-1$.

  3. 3.

A single component of the form

            component Base|V| provides base|V|
                       requires vertStat|V| {
             void callBase|V|(Input I, int[] vS) {

                 vS[|V|] = vertexStatus|V|()

                 numFound = 0
                 for j = 1 to |V| do
                     if vS[i] == i then
                        numFound = numFound + 1
                 if numFound = k then
                     isCandidatekDomSet = True
                 else
                     isCandidatekDomSet = False

                 if isCandidatekDomSet then
                     numFound = 0
                     for i = 1 to |V| do
                         if v_I(x_i) and vS[i] == 1 then
                             numFound = numFound + 1

                     if numFound > 0 then
                         output 1
                     else
                         output 0
                 else
                     output = 0
             }
        }

  4. 4.

A set of $|V|$ components of the form

            component VertexStatusJ provides vertStatJ {
                              requires domSetStat
             int vertexStatusJ() {
                 return domSetStatus()
             }
        }

for $1\leq{\tt J}\leq|V|$.

  5. 5.

Two components of the form

            component DomSetStatus0 provides domSetStat {
             int domSetStatus() {
                 return 0
             }
        }

        component DomSetStatus1 provides domSetStat {
             int domSetStatus() {
                 return 1
             }
        }

Finally, let $c$ be component Base in $L_{comp}$. Note that the instance of
CSCreatepoly described above can be constructed in time polynomial in the size
of the given instance of Dominating set; moreover, as there are only single-
level loops in the component code that each execute at most $|V|<|I|$ times,
any component-based software system created relative to $L_{int}$, $L_{comp}$,
and $c$ runs in time linear in the size of input $I^{\prime}$.

Observe that interfaces base, vertStatJ for $1\leq{\tt J}\leq|V|$, and
domSetStat and components VertexStatusJ for $1\leq{\tt J}\leq|V|$,
DomSetStatus0, and DomSetStatus1 are the same as in the reduction in the proof
of Result A.9. Moreover, interfaces base and baseJ, and components Base and
callBaseJ, $2\leq{\tt J}\leq|V|$, effectively simulate interface base and
component Base in the same reduction. Hence, the proof of correctness of the
reduction in the proof of Result A.9 can, with slight modifications, also
proves the correctness of the reduction described above. Given the
$NP$-hardness of Dominating set, this reduction implies that CSCreatepoly is
$NP$-hard when $I_{ci}=2$, $C_{pi}=1$, and $C_{ri}=2$, and hence by Lemma 3
not fp-tractable relative to these parameters unless $P=NP$. The fp-
intractability result for ESCreatepoly then follows by contradiction from
Observation 1.

Figure 9: General structure of valid software systems created by the reduction
in the proof of Result A.11. Note that index $x$ in DomSetStatusx is such that
$x\in\\{0,1\\}$. Following the convention in Figure 3, interfaces with
multiple implementing components are enclosed in dashed boxes.

Let us now prove Result A.11. The reduction below modifies that given in the
proof of Result A.9 such that there are still only two components
DomSetStatus0 and DomSetStatus1 but now, each of these components contains
customized versions of procedures vertexStatus1(), vertexStatus2(), …,
vertexStatus|V|() instead of placing these procedures separately in components
VertexStatus1, VertexStatus2, …, VertexStatus|V| (see Figure 9). By invoking
the abilities of different interfaces to implement different copies of the
same component and implementing components to provide to an interface only
that code which is used by that interface, not only is the maximum component
depth reduced by one but the size of the component library $L_{comp}$ is
reduced to a constant (namely, 3).

Result A.11

For any choice of $Rew()$ and $Env()$, if
$\langle|L_{comp}|,I_{ci},S_{depth}\rangle$-ESCreatepoly is fp-tractable then
$P=NP$.

Proof: Consider the following polynomial-time Karp reduction from Dominating
set to CSCreatepoly: given an instance $I=\langle G=(V,E),k\rangle$ of
Dominating set, construct an instance $I^{\prime}=\langle
R,L_{int},L_{comp},c\rangle$ of CSCreatepoly in which $R$ is the same as that
given in the reduction in the proof of Lemma 4. Let $L_{int}$ consist of
$|V|+1$ interfaces broken into two groups:

  1. 1.

A single interface of the form

            interface base {
             void main(Input I)
        }

  2. 2.

A set of $|V|$ interfaces of the form

            interface vertStatJ {
             int vertexStatusJ()
        }

for $1\leq{\tt J}\leq|V|$.

Let $L_{comp}$ consist of $3$ components broken into three groups:

  1. 1.

A single component of the form

            component Base provides base
                       requires vertStat1, vertStat2, ...,
                                vertStat|V| {
             void main(Input I) {

                 create integer array vS of length |V|

                 vS[1] = vertexStatus1()
                 vS[2] = vertexStatus2()
                     ...
                 vS[|V|] = vertexStatus|V|()

                 numFound = 0
                 for i = 1 to |V| do
                     if vS[i] == i then
                        numFound = numFound + 1
                 if num_found == k then
                    isCandidatekDomSet = True
                 else
                    isCandidatekDomSet = False

                 if isCandidatekDomSet then
                     numFound = 0
                     for i = 1 to |V| do
                         if v_I(x_i) and vS[i] == 1 then
                             numFound = numFound + 1

                     if numFound > 0 then
                         output 1
                     else
                         output 0
                  else
                     output 0
             }
        }

  2. 2.

Two components of the form

            component DomSetStatus0 provides vertStat1, vertStat2, ...
                                         vertStat|V| {

             int vertexStatus1() {
                 return 0
             }

             int vertexStatus2() {
                 return 0
             }

             ...

             int vertexStatus|V|() {
                 return 0
             }
        }

        component DomSetStatus1 provides vertStat1, vertStat2, ...
                                         vertStat|V| {

             int vertexStatus1() {
                 return 1
             }

             int vertexStatus2() {
                 return 1
             }

             ...

             int vertexStatus|V|() {
                 return 1
             }
        }

Observe that in component Base, if entry $i$ of array vS has value $1$ then
vertex $i$ is in the candidate dominating set for $G$ encoded in vS. Finally,
let $c$ be component Base in $L_{comp}$. Note that the instance of
CSCreatepoly described above can be constructed in time polynomial in the size
of the given instance of Dominating set; moreover, as there are only a single
$|V|$-length assignment block and two single-level loops in the component code
that each execute at most $|V|<|I|$ times, any component-based software system
created relative to $L_{int}$, $L_{comp}$, and $c$ runs in time linear in the
size of input $I^{\prime}$.

Let us now verify the correctness of this reduction:

  * •

Suppose there is a dominating set $D$ of size at most $k$ in the given
instance of Dominating set; if $|D|<k$, augment $D$ with $k-|D|$ arbitrary
other vertices from $G$ such that $|D|=k$. Construct a component-based
software system consisting of $c$ and $|V|$ copies of the domSetStatus
components in which the vertStatJ interface in component Base is implemented
by component DomSetStatus1 if vertex J is in $D$ and by component
DomSetStatus0 otherwise. Observe that for each $(i_{j},o_{j})\in R$, this
software system produces output $o_{j}$ given input $i_{j}$.

  * •

Conversely, suppose that the constructed instance of CSCreatepoly has a
working component-based software system based on $c$ relative to $L_{int}$,
$L_{comp}$, and $R$. In order to accommodate all input-output pairs in $R$,
the $|V|$ vertStatJ interfaces in component Base must be implemented by
domSetStatus components such that the produced values in array vS specify a
dominating set of size $k$ in $G$. Hence, the existence of a working
component-based software system for the constructed instance of CSCreatepoly
implies the existence of a dominating set of size $k$ for the given instance
of Dominating set.

The reduction above is thus correct. Given the $NP$-hardness of Dominating
set, this reduction implies that CSCreatepoly is $NP$-hard when
$|L_{comp}|=3$, $I_{ci}=2$, and $S_{depth}=2$ and hence by Lemma 3 not fp-
tractable relative to these parameters unless $P=NP$. The fp-intractability
result for ESCreatepoly then follows by contradiction from Observation 1.

Finally, let us prove Result B.22. This result addresses the feasibility of
preprocessing a fixed portion of the input to an intractable problem to create
polynomial-size information that can be used to solve future instances of that
problem relative to a varying portion of the problem input in polynomial time.
This will be evaluated using the computational complexity framework described
in [37]. The input to a problem of interest will be considered as a pair
$\langle x,y\rangle$, where $x$ is the fixed part and $y$ is the varying part.
As we will focus here on decision problems like CSCreatepoly in the main text
whose solution is either “Yes” or “No”, each such problem will be considered a
language of pairs. An example of such a problem is

C-SAT $=\\{\langle(f),(p)\rangle~{}|~{}p$ can be extended to a truth
assignment satisfying $f\\}$

where fixed part $f$ is a formula in conjunctive normal form (a set
$C=\\{C_{1},C_{2},\ldots C_{n}\\}$ of clauses AND-ed together where each
clause is a set of negated or unnegated Boolean variables, e.g., $(v_{1}OR\neg
v_{2}ORv_{4})AND(v_{2}ORv_{3})$) over a set of Boolean variables
$V=\\{v_{1},v_{2},\ldots,v_{m}\\}$ and varying part $p$ is a partial truth
assignment to the variables in $V$. Consider the following reducibility
between such problems.

###### Definition 4

[37, Definition 2.8] A $||{\leadsto}$ reduction between two languages of pairs
$A$ and $B$ is a triple$f_{1},f_{2},g)$ where $f_{1}$ and $f_{2}$ are poly-
size unary functions and $g$ is a binary polynomial-time function such that
for any pair of strings $\langle x,y\rangle$ it holds that:

$\langle x,y\rangle\in A$ if and only if $\langle
f_{1}(x,|y|),g(f_{2}(x,|y|),y)\rangle\in B$

It is known that C-SAT is hard under $||{\leadsto}$ reductions relative to a
class ${||{\leadsto}}NP$ [37, Section 3.1] and hence not preprocessable in the
sense above unless the Polynomial Hierarchy $PH$ collapses, i.e.,
$PH=\Sigma^{r}_{2}$ [37, Theorem 2.12].555 Aficionados of [37] will protest
that by Theorem 2.12, our result implies that the Polynomial Hierarchy only
collapses to $\Sigma^{p}_{3}$. However, when that theorem is combined with the
Karp-Lipton Theorem [56] (the most typical version of which states that if
$NP\subseteq P/Poly$ then $PH=\Sigma^{p}_{2}$), we can strengthen Theorem 2.12
to give our stated result.  We will now prove the result by a reduction based
on that in the proof of Result A.9 (see Figure 10).

Figure 10: General structure of valid software systems created by the
reduction in the proof of Result B.22. Note that index $x$ in TruthValuex is
such that $x\in\\{True,False\\}$. Following the convention in Figure 3,
interfaces with multiple implementing components are enclosed in dashed boxes.

Result B.22:

If ESAdaptpoly can have $L_{int}$, $L_{comp}$, $R$, and $c$ preprocessed to
create polynomial-size information that can be used to solve ESAdaptpoly
instances of arbitrary $S$, $Rew()$, and $k$ in polynomial time then the
Polynomial Hierarchy $PH$ collapses, i.e., $PH=\Sigma^{p}_{2}$.

Proof: Consider the following $||{\leadsto}$ reduction from C-SAT to
CSAdaptpoly: given an instance $I=\langle(f),(p)\rangle$ of C-SAT, construct
an instance
$I^{\prime}=\langle(R,L_{int},L_{comp},c),\linebreak(S,Rew(),k)\rangle$ of
CSAdaptpoly in which $R$ has a single input-output pair $\\{True,1\\}$. Let
$f^{\prime}$ be the version of $f$ in which there is a new Boolean variable
$x_{m+1}$ that is OR-ed into every clause and $p^{\prime}$ be the version of
$p$ such that $x_{m+1}=False$. Let $L_{int}$ consist of $m+3$ interfaces
broken into three groups:

  1. 1.

A single interface of the form

            interface Base {
             void main(Input I)
        }

  2. 2.

A set of $m+1$ interfaces of the form

            interface varAssignJ {
             Boolean varAssignJ()
        }

for $1\leq{\tt J}\leq m+1$.

  3. 3.

An interface of the form

            interface truthValue {
             Boolean truthValue()
        }

Let $L_{comp}$ consist of $m+4$ components broken into three groups:

  1. 1.

A single component of the form

            component Base provides base
                       requires varAssign1, varAssign2, ...,
                                varAssignm {
             void main(Input I) {

                 create Boolean array vA of length m

                 vA[1] = varAssign1()
                 vA[2] = varAssign2()
                     ...
                 vA[m+1] = varAssign(m+1)()

                 if truth assignment vA satisfies f’ then
                     output 1
                 else
                     output 0
             }
        }

  2. 2.

A set of $m+1$ components of the form

            component VarAssignJ provides varAssignJ {
                             requires truthValue
             Boolean varAssignJ() {
                 return truthValue()
             }
        }

for $1\leq{\tt J}\leq m+1$.

  3. 3.

Two components of the form

            component TruthValueFalse provides truthValue {
             Boolean truthValue() {
                 return False
             }
        }

        component TruthValueTrue provides truthValue {
             Boolean truthValue() {
                 return True
             }
        }

Observe that in component Base, if entry $i$ of array vA has value $True$
($False$), then variable $i$ in the candidate truth-assignment for $f$ encoded
in vA has value $True$ ($False$). Let $c$ be component Base in $L_{comp}$ and
$S$ be the component-based software system consisting of Base and VarAssign1,
VarAssign2, …, VarAssign(m+1) such that varAssign(m+1)() is implemented by
TruthValueTrue and all other varAssignx(), $1\leq{\tt x}\leq m$, have a random
implementation relative to TruthValueFalse and TruthValueTrue. Observe that
courtesy of the truth-setting of $v_{m+1}$ encoded in $S$, each clause in
$f^{\prime}$ is satisfied and $S$ will output 1 on any input. Finally, let
$Rew(S^{\prime\prime})$ return the number of variable-assignments in the
truth-assignment for $f^{\prime}$ encoded in component-based system
$S^{\prime\prime}$ that differ from those in the partial truth-assignment
$p^{\prime}$ and set $k=0$. Note that the instance of CSAdaptpoly described
above can be constructed in time polynomial in the size of the given instance
of C-SAT and that this construction encodes the required functions $f_{1}()$,
$f_{2}()$, and $g()$ in the definition of $\leq_{comp}$-reducibility;
moreover, any candidate software system created relative $L_{int}$,
$L_{comp}$, and $c$ runs in time linear in the size of input $I^{\prime}$.

Let us now verify the correctness of this reduction:

  * •

Suppose there is a satisfying assignment $p^{\prime\prime}$ that extends $p$
and satisfies $f$. Construct a component-based software system $S^{\prime}$
consisting of $c=$ Base and VarAssign1, VarAssign2, …, VarAssign(m+1) such
that varAssignx(), $1\leq{\tt x}\leq m$, implements the TruthVValue component
corresponding to the value of $v_{x}$ in $p^{\prime\prime}$ and
varAssign(m+1)() implements TruthValueFalse. Observe that for the only
requirement $r\in R$, this software system produces output $1$ given input
$True$; moreover, $Rew(S^{\prime})=0\leq k=0$. Hence, the existence of a
satisfying truth-assignment that extends $p$ and satisfies $f$ in the given
instance of C-SAT implies the existence of a working component-based software
system $S^{\prime}$ for the constructed instance of CSAdaptpoly such that
$Rew(S^{\prime})\leq k$

  * •

Conversely, suppose that the constructed instance of CSAdaptpoly has a working
component-based software system $S^{\prime}$ based on $c$ relative to
$L_{int}$, $L_{comp}$, and $R$ such that $Rew(S^{\prime})\leq k$. As $k=0$, by
the definition of $Rew()$, this means that the truth-assignment to the
variables in $V$ encoded in $S^{\prime}$ cannot differ from any of the
variable assignments in the partial truth-assignment $p^{\prime}$. As
$v_{m+1}=False$ in $p^{\prime}$, this means that the truth-assignments to the
remaining variables in $V$ (i) are an extension of $p$ and (ii) encode a truth
assignment that satisfies $f$. Hence, the existence of a working component-
based software system for the constructed instance of CSAdaptpoly such that
$Rew(S^{\prime})\leq k$ implies the existence of a satisfying truth-assignment
that extends $p$ and satisfies $f$ in the given instance of C-SAT.

The reduction above is thus correct. Given the ${||{\leadsto}}NP$-hardness of
C-SAT, this reduction implies that CSAdaptpoly is ${||{\leadsto}}NP$-hard as
well and not preprocessable in the sense of [37] unless the Polynomial
Hierarchy $PH$ collapses, i.e., $PH=\Sigma^{p}_{2}$ (see the discussion
immediately prior to this proof). The same non-preprocessability result for
ESAdaptpoly then follows by contradiction from Observation 1.