extfieldsofstudy:
Engineering
Computer Science

text:
GreenMail: Reducing Email Service's Carbon Emission with Minimum Cost

Internet services contribute a large fraction of worldwide carbon emission nowadays, in a context of increasing number of companies tending to provide and more and more developers use Internet services. Noticeably, a trend is those service providers are trying to reduce their carbon emissions by utilizing on-site or off-site renewable energy in their datacenters in order to attract more customers. With such efforts have been paid, there are still some users who are aggressively calling for even cleaner Internet services. For example, over 500,000 Facebook users petitioned the social networking site to use renewable energy to power its datacenter. However, it seems impossible for such demand to be satisfied merely from the inside of those production datacenters, considering the transition cost and stability. Outside the existing Internet services, on the other hand, may easily set up a proxy service to attract those renewable-energy-sensitive users, by 1) using carbon neutral or even over-offsetting cloud instances to bridge the end user and traditional Internet services; and 2) estimating and offsetting the carbon emissions from the traditional Internet services. In our paper, we proposed GreenMail, which is a general IMAP proxy caching system that connects email users and traditional email services. GreenMail runs on green web hosts to cache users' emails on green cloud instances. Besides, it offsets the carbon emitted by traditional backend email services. With GreenMail, users could set a carbon emission constraint and use traditional email service without breaking any code modification of user side and email server side.

Today more and more applications "talk" to Internet services everyday as well as providing their own services to other applications. However convenient and efficient for developers to use, Internet services do witness a significant growing in terms of their carbon footprint as they become increasingly popular. It has been estimated that by 2020, the annual carbon emission of major datacenters worldwide would likely to exceed the footprint of the entire Netherlands [3]. While individual Internet applications and services like Twitter and Facebook are under public pressure that they should reduce their carbon emission [1,4], public content delivery networks (CDN) providers need to find more value-added features to attract customers, many of which concern the "carbon" impact of services they use [5].
Reducing the carbon footprint of a datacenters has been widely studied in academia: most of efforts are trying to solve the problem inside the datacenters [2， 6,7,8], or Internet services [9]. While previous approaches are all concrete work, making changes in either existing datacenter infrastructures or Internet services is not that easy mainly because of two reasons: the transition cost could be too high for the expected benefits to offset, and the new modules dealing with carbon footprint may not be stable or compatible enough to interact with the legacy components, especially during the transition phase. However, some users may simply want to achieve certain carbon emission level that current datacenter and renewable technology cannot suffice.

2
To address the gap between users' demand to be "green" and current development of datacenters and Internet services, we borrow the idea of CDN, i.e. caching frequently accessed content near to end users, proposing a framework of independent operated Internet service that is running under certain carbon constraints, while maintaining the low cost. Directed by this idea, we design GreenMail as our proof-of-concept prototype system. It is an IMAP proxy running on green web hosts [2] and sitting between email client software (e.g. Thunderbird or IPhone built-in email client) and IMAP servers from traditional email service provider like Gmail and Hotmail. Green hosts are defined as web-hosting services providing cloud instances operated under some carbon constraints.
Using green host instances, any operation happened inside the GreenMail is guaranteed to meet certain carbon emission level, e.g. carbon neutral. Users bind their email account to GreenMail, linking the backend email server at traditional email service provider side to our IMAP proxy. They access their emails through GreenMail. GreenMail reduce carbon footprint by caching the recent accessed emails on green host instances; upon another user access on the same email, GreenMail directly dispatches the local copy of the email to the user. If the email is not exist in local cache, then GreenMail retrieves the email from "dirty" remote server, cache it and purchases renewable energy credits (REC) to offset the estimated carbon footprint occurred by retrieval operation, if necessary.
There are two ways by which GreenMail capping its carbon footprint: (1). Operate on green hosts, so that the carbon emissions caused by local operations (i.e. operations inside GreenMail) is neutralized. By using caching mechanism, most operations are localized.

3
(2) Purchase renewable energy credits from energy markets, so that the estimated carbon emission from remote email servers is neutralized.
The research challenges here are also pretty straightforward: (1) We need to answer the following question: At given point of time, how many instances should we keep for our system and how many REC do we need to buy to meet both carbon constraint and cost constraint? We could of course keep as many as possible instances to capture almost all the data in memory to make our response time fair quickly; or buy enough REC to make it unlimitedly "green". But we cannot forget both green instances and REC cost money. To sufficiently answer the above question, an optimization model to characterize the cost is desired.
(2) In order to offset the carbon footprint caused by retrieving content from dirty servers, our system must be able to find a reasonable way to estimate carbon emission of remote servers and network links that it has limited knowledge on.
The contributions of this work are three folds: (1) Mathematically characterize the cost to operate a green CDN-like caching system.
(2) Build a prototype system GreenMail, analyzing the system's cache behavior against both synthetic and real-world load.
(3) Properly estimate carbon emission occurred during the email transmission phase when cache system retrieves content from dirty servers.

Chapter 2: Related Work
This paper models a type of Internet services which bridges existing Internet services while maintain a low cost. Our model studies how to find a configuration to minimize the cost and be efficient as well. In this section, we outline related work in these areas.
Given the intermittent natural of renewable energy, integrating on-site renewable energy generators to datacenters is challenging. Internet services may reduce their carbon footprint by deciding when, if ever, to process requests. Or a service may drop requests and turn off machines (or put them into low-power state) to use less dirty energy. Blink [8] proposed a key-value storage service that transferred popular keys away from nodes that were turned off during intermittent clean energy outages. The challenge was to serve as read and write requests as possible using only resources powered by renewable energy.
Li et al. [11] turned off processor cores to increase the ratio of renewable energy to dirty energy on a system. Similarly, Gmach et al. [12,13] found that server-power capping and consolidation to power servers under low renewable-energy production could enable renewable powered services, albeit with a performance penalty. Deng et al. [6] studied the impact of different approaches to integrate grid ties to power delivery systems inside datacenters. All works mentioned above require more or less changes inside datacenters' infrastructures.

5
To control the carbon footprint, a service provider could also distribute user requests to datacenters with higher renewable energy production among multiple datacenters that are geographically located in different places. Le et al. [14] studied services that capped their carbon footprints either by cap-and-trade, cap-and-pay or absolutely capped policies. Their key insight was that a central load balancer could route requests between green and dirty datacenters worldwide to maintain a low carbon footprint while meeting SLAs. Zhang et al. [10] studies services that tried to minimize the carbon footprint of certain requests within a fixed budget. Liu et al. [15,16] proposed a model to assess a datacenter's performance in terms of carbon footprint efficiency. They use weighted linear models to find the best host, proposing a scalable algorithm to do so.
The above works all requires changes either within existing Internet services or datacenters.
Our work differs from previous works, as it is an independent Internet service outside existing infrastructures. GreenMail works as an add-on proxy layer to existing email services and users could switch between GreenMail service and traditional email services seamlessly. GreenMail's goal is not only to operate under a pre-set carbon footprint, but also to offset the estimated carbon footprint from traditional Internet services that are used but outside GreenMail itself. Besides controlling the carbon footprint, GreenMail has to cost as little as possible to reduce the operating cost.

Chapter 3: Minimizing Cost under Constraints
Our optimization model is to stay carbon neutral and minimize the cost while maintain a relatively low response time. In this section, we first show the optimization formula and then discuss the possible optimal solution under difference circumstances.

Optimization Model
The goal of our optimization model is to minimize the capital cost. The cost of GreenMail consists of two parts: 1) The cost to buy renewable energy credit (REC), and 2) the cost to buy green instances from green hosts. Note that the instances are usually paid on demand. For example, in GreenQloud, a green cloud provider, a medium Linux instance with 1 core, 1GB RAM and 40GB disk storage costs $0.036/hour, or $26.28/month [17].
Before purchasing any renewable energy credits, we need to estimate the possible carbon emission needs to be offset. A user request is first delivered to GreenMail through normal TCP connection, which may cause carbon emissions along with this route. If the requested email is in the GreenMail's cache, it is considered as a cache hit, then the email is sent back to the user and there is no other carbon emissions, except the emission along the link back to the user; otherwise, it is a miss, and then the GreenMail retrieves the email from remote email server, which causes carbon emission from the remote email server and the round-trip network link. Figure 1 shows an overview of GreenMail.

7
Suppose the user requests arrival rate is λ, given a time period T, the carbon emissions consists of the following parts (the unit is normalized to Joules): • The emission of the link between the user and GreenMail: λTu, where u is the carbon emission along the link of one request.  Beside these emissions, there may be additional renewable energy from green host instances to offset some part of the emissions described above. GreenMail works on green hosts' instances. For most green hosts, they lease their instances under some prefixed offset ratio [2]. Here the offset ratio means the ratio of total renewable energy 8 (or renewable energy credits) to the total energy consumption. For example, a 100% offset ratio means the instances only consume renewable energy. Because of renewable energy credits, green hosts may buy additional amount of credits from market to over offset their carbon emission, which makes it is possible for the ratio to be greater than 100%. For example, Green Geeks [18] offers 300% offset ratio, meaning for every Joules of energy used, there are two additional Joules of renewable energy, which could be used to offset the carbon emissions from other places.
To utilize the "over offsets" from green hosts, GreenMail pre-set an offset target ratio for the whole system. The part of such "over-offset" will then be distributed to offset emissions. The additional carbon offset is: NE v (r − r T ), where E v is the energy consumption of one instance in GreenMail; r is the offset ratio offered by green host; r T is the operating offset ratio of GreenMail.
Assuming the unit cost of renewable energy credits is c0 ($/J), and then the cost of renewable energy credits is: Besides the cost of renewable energy credits, another part of the cost is the cost on purchasing instances from green hosts. Assuming the unit price of one in-stance is cv, and then given N instances and within time T, the cost of the instances is: The total cost of GreenMail is the summation of these two parts of cost is: To ensure service quality of certain SLA, GreenMail has to maintain its processing rate above certain level. Suppose for each instance, the processing rate is β (req/s), and then we have the following constraint for GreenMail is: meaning the processing rate of the whole system (βN) should be greater than or equal to the arrival rate (λ).
In conclusion, the optimization model for GreenMail is shown in (5). The notations used in (5) are listed in Table 1. Note the notations followed by a "*" means we need to estimate reasonably, which we will discuss in coming sections.

Brief Analysis on the Optimization Model
The optimization model shown in (5) is a non-linear optimization model because of the unknown function M(N). Due to the vicissitudes of the network environment, users' behavior and different cache mechanism, the miss rate function may vary wildly.
To solve our optimization problem, we need to at least make some assumptions on the miss rate function. These assumptions will be validated by experiments in Section 5.
Without loss of generality, we can safely make the following assumptions about the miss rate function M(N).
• M(N) ≥ 0 and Lim !→! = 0. This is saying the miss rate will never be negative and it reaches zero if we have infinite number of instances.
• M(N) is a monotonically decreasing function. This means with more instances, the miss rate will never be higher.
• M(N) decreases dramatically when N is small; while decreases insignificantly when N is large. This means adding more instances may contribute little to decrease miss rate if we are already using large number of instances. It also suggests that if we have infinite number of instances, adding more instances will not change the miss rate.
All assumptions are made based on our understanding of a typical cache and validated by experiments in Section 5. Some of them may be not always held. For example, under some scenario with certain cache mechanism, the miss rate may increase even if the resources are increased. However, those assumptions will be held in most 11 cases for a well-designed cache given a normal user access pattern.
In this section we first prove the existence of the optimal solution. We consider (3) as carbon constraint and (4) as SLA constraints. We will drop the SLA constraint and prove that the cost function has a minimum point. Then we add the constraint back to get the optimal solution under different conditions.

Proof that we could always find a global minimum for the cost function:
To get the global minimum, we calculate the first derivative of (3): λ, c0, T, G, H, Ev, r, r T and cv are all positive values and r > r T . We can then simplify the notation in (3) to: If ! ≤ 0, then (6) will always be less than 0, the only constraint we need to satisfy is the SLA, which is ≥ ! ! according to (4); or when ! > 0, we could say a minimal point may exist at when . However, to prove it is the global minimum, we first need to prove it is a minimum for (3), and then prove there is no other point making the cost function smaller.
We take the second derivative of (3), which is Based on the second and third assumptions on the characteristics of M(N), we (8) would always be greater than zero (9). As a result of (9) we could know there would be one and the only one minimal point when N satisfies Finally, consider the SLA constraint. Suppose the !"# is the minimum point we get from above: • If N min ≥ ! ! , then Nmin is the solution to the optimization problem.
• If Nmin < ! ! , then ! ! is the solution to the optimization problem.
As a conclusion, we could safely say 1) if ! ≤ 0, the cost function will always increase with N being greater; and thus the only constraint for N comes from to satisfy the SLA, which is ! ! . 2) If ! >0, we first calculate the minimal N to satisfy the carbon constraint and then check if it could also satisfy SLA constraint: N must at least meet the SLA constraint.

Chapter 4: System Design and Implementation
We leverage several open source software to implement our prototype system.
The system includes the GreenMail itself and the synthetic user as well as an IMAP server. Specifically, in GreenMail we use SquirrelMail [19] as front-end from where users could access our service, Redis [20] as our in-memory key-value store used to caching users email. We use Apache Jmeter [21] to simulate the concurrent user requests to the GreenMail web interface and Mstone [22] to conduct the pressure test against MantisMail [5], a pure IMAP proxy version of GreenMail developed by us in another related project. Dovecot [23], an open source IMAP server is used in our system. Figure 2 shows how the above components interact. We will discuss about each component of our system in the following sections. where user interacts with our service and the back-end is where we cache the email.
We implement our front-end by modifying SquirrelMail, an open source webmail package written in PHP, which supports IMAP and SMTP protocol. FETCH commands, which are to retrieve emails content from server in IMAP context, are cached by our system. We let SquirrelMail always first try to retrieve email from Redis; if it is not there then we have to issue request to the IMAP server. Figure 3 shows the pseudo code of this procedure.

Figure 3 Pseudo Code of Cache Look-up
The back-end is Redis instances. Redis is an in-memory key-value store for small chunks of arbitrary data (strings, objects) from results of database calls, API calls, or page rendering. By doing caching everything in memory, Redis has significantly reduced the access latency and the load on the persistent storage, which is IMAP server in our case. But in our context, it will also reduce the carbon footprint IMAP server and the link cost to the server.
Redis is typical client-server architecture. Its special designed hash mechanism makes it is pretty scalable, since which instance is chosen to store the item is calculated 16 merely by client side library. It is users' responsibility to ensure each client has the exactly same server list. Redis servers know nothing about each other and no communication is required among server nodes. Redis takes advantage of consistent hashing [24], it minimizes the remapping when the overall hash table resizes. Thus, there is very low miss rate incurred when new nodes are added in or deleted from the cluster.

Other Components
In order to simulate multiple users accessing the email service based on some pattern, we use Apache Jmeter to generate concurrent user requests. We create scripts to randomly generate requests against uniform and Gaussian distributions. The inter-arrival times are Poisson distribution. To conduct pressure test on the system, we also leverage Mstone, a multi-protocol stress and performance measurement tool. We will discuss this in more detail in next section.
To build a controllable environment, we use Dovecot to set up an IMAP server treating it as a remote public email service provider. Since IMAP service is generally available among most email providers like Gmail, Yahoo, GreenMail can seamlessly transit to those major providers.

Figure 4 Time Sequences of Typical Accesses to GreenMail
A typical access is shown as in Figure 4. The user first sends an IMAP command of LOGIN to log into the IMAP server, and then opens some email by send FETCH command. Upon intercepting a FETCH command, GreenMail first tries to find the email among Redis clusters. If the corresponding email could be found, then it is a cache hit and there is no need to further resort to IMAP server; Otherwise GreenMail let the FETCH command go through itself. The IMAP server would respond to this FETCH with OK FETCH completed. After caching this email, GreenMail forwards it to the user.
Note that since GreenMail is on green host, we will eliminate the possible carbon cost 18 introduced by accessing IMAP server.
As mentioned before, we also need to estimate the carbon footprint outside For link cost (G and u in table 1), we need to consider both users to GreenMail (u) and GreenMail to remote servers (G). While u is quite hard to capture since user accesses could happen anywhere from any device; G is relatively fixed given that we only have limited number of IMAP servers and their "IP:Port" are also fixed. However, we could estimate u+G by multiplying average Internet Energy Intensity (kWh/GB) [26] with the inbound traffic (GB). Obviously, such estimation is rough because here we assume the Internet is "flat" in terms of energy consumption. But we could have better estimation if we could have more information on carbon footprint and load of passed routers. For the carbon emission from GreenMail to dirty servers, our system traces each routers from GreenMail to IMAP server, converting IPs to a serial of geo-locations and then according to some published data source, we could know how much of the carbon emission per unit energy at that locations. For example, we could know a router/switch with IP 164.107.2.150 is located at Columbus Ohio, where 1030 Kilograms of CO2 emitted per (net) megawatt-hour of electricity produced. The remaining is just to find some average energy consumption of those routers. For example, from [26], we know that a typical router cost 2.4 TWh per year. While this estimation is pretty rough, our argument is it is enough for us to understand the carbon footprint of the GreenMail and its potential users.
While above estimations make sense in some reasonable way, further mathematical estimation suggests the link carbon cost might be dropped in practice.
According to [26], we know in 2006 typical server annual energy consumption is 24.5 TWh and Internet Energy Intensity is 24.kWh/GB. Assume each email user has 50 emails daily, and each of email size is 0.1 MB. We also assume an aforementioned server could serve ~500 users. Then we know the transmission cost would be 22173kWh, which is only 1/1,000,000 of 24.5TWh. In this sense, we could argue that the link cost in our formula could be ignored in our real implementation.

Chapter 5: Experiments
In this section, we will present three sets of experiments on our system: one is using synthetic workload, one is real world test, and the other is a performance comparison between with our IMAP Proxy and without our proxy.

Simulation On Our System
For the synthetic workloads, we use Jmeter to generate user accesses against certain distributions; also, we use Mstone to test how well our system could be when access pressure is high.

Characterizing Caching Behavior
In Section 3, we mentioned the three assumptions about the miss rate function M(N). In this section, we set up several experiments to validate those assumptions.
We did our experiment on one Redis instance and configure it to be different sizes, i.e. 4MB, 8MB and 16MB. We do our experiment only on one Redis instance is simply because the goal is to characterize the property of caching behavior with a growing capacity of cache. The tiny capacity of cache in our setup is corresponding to the small size of email content we generated. Email size is against Gaussian distribution with   In Section 3, we made three assumptions against miss rate function M(N). The above graphs also agree on the assumptions.
First, for assumption 1 and 3, comparing Figure 6(b) to Figure 6(c), when cache size is large enough, we will not see obvious miss rate reduction, especially when compared to Figure 6(a) to Figure 6(b). Intuitively, given fixed amount of user as well as their fixed requests rates, the storage space needed is also fixed. This makes there will be few to no benefits in terms of miss rate decrease since we have already cached everything 24 that may be accessed. Therefore we could safely expect zero miss when cache size is enough large.
Second, M(N) is a monotonically decreasing function. Note when cache size grows, fewer cache misses are observed. For 8MB cache and 16 MB cache instance, we barely see a miss after certain time.

Performance Test against MantisMail
To get a better understanding on performance difference between with and without our proxy system, we leverage Mstone to conduct performance test against our system. Mstone [22] is a multi-protocol stress and performance measurement tool, which could test multiple protocols including IMAP simultaneously and measures the performance of every transaction. Figure 7 shows the IMAP commands per second of both w/ vs. w/o our proxy. It suggests that our proxy bring down the system average performance by 42%. This large performance deduction is mainly due to our proxy's current debug version implementation will encrypt, compress and persist the content of each command we cached. Table 2 shows the comparison in terms of processing time for each IMAP command. Note that not all types of IMAP command are equally "quick" to process, e.g.

Figure 7 IMAP Commands per Second
LOGIN is slower than most of other IMAP commands. We see the same performance degrade in terms of processing time. With our proxy, its average processing time for w/ proxy is much longer than w/o proxy. Note with proxy, we actually "smooth" the processing rate for each IMAP commands, since we do caching in our proxy. The duration of time to retrieve content from local cache for different commands are similar.
That's why we have a smaller standard deviation for w/ proxy.  Figure 8 compares throughputs. "Bytes read" means how many bytes are in the data flow from tested system to user; "bytes write" is how many bytes are written out through user (Mstone here). We use server here to denote IMAP server or our caching system; Mstone is client in this context. Figure 8 suggests we always "get" more from server than set to the server. This means we are benefiting from caching frequent accessed objects. Performance degrade appears this figure again for the same reason as mentioned before.
As a conclusion for this experiment, we can say we get benefit by using our system; but the tradeoff is a performance drop. However, we make an argument this degraded performance is mainly because of we did the entire test against our "debugging" version system, which enable a large amount of logging and encrypt and compression. Along with a web interface for user to access their emails, we also have a pure IMAP proxy system that is built under same idea with GreenMail. We argue that actually nowadays people tend to access their email from some mobile devices other than through a web interface. Thus being a part of our experiment to see how our system would act in the real world, we deploy the system in GreenQloud, one of well-known green hosts. And three members of our group including the author himself used the system for two days.
We all bind our email clients, such like Thunderbird or Outlook on PC, or iPhone/android built-in email software to the system. Our system logged all the email access and hit/miss activities. Figure 9 shows the share of hits and misses compared to all accesses; Figure 10 shows bytes transferred for all misses and all hits. The numbers here are not that big is because: 1) only three people using the system; 2) The experiment was conducted during weekend instead of busy workdays.
28 Figure 9 Numbers of Hits vs. Misses Figure 10 Data Transferred on All Misses vs. All Hits Figure 9 also shows us that we got 12% of cache hit for all cache accesses in two days, which is actually a pretty big number for a CDN like system. Figure 10 tells the or manually open to read an email multiple times. Only the clients automatically connect to pull emails. If we bind more devices under same user, we could expect higher hit rate.
It is because most email client software would always periodically check the inbox with different frequency, if one email is accessed by one client and after first miss, the email would be cached and all the following access from other devices would only lead hits.
Luckily, what we expect is the way that people accessing their email nowadays. Usually we connect same email accounts from our PCs at work, cellphones, PDAs, laptops, etc.
The fact that ratio of "hit_bytes" to "miss_bytes" is smaller than that of number of hits to number of misses suggests that in terms of size of transferred data we may not further benefit that much from caching other IMAP commands such like LIST, which is used to list the tittle of email in an inbox, even though we may get a higher hit rates if we do so; it is because only the FETCH command get the real content of email, which makes up the majority of network traffic for IMAP communication.

Operating Cost Estimation
And then, how much do we need to pay for if we run this experiment system for one year? We suppose our system is carbon neutral, i.e. rT=100%. r is also 100% as GreenQloud is carbon neutral, rather than providing over-offsetted ratio that is greater than 100%. For simplicity, we let N=1. Assume after cache is warmed, the miss rate would be 88% when system is stable as our experiment suggests. Link costs, which include G and u, are ignored. We aggregate the server energy cost by using Google's published data [25], which is 14,200 kWh/year. We let c0 equal to 6. Conclusion In this paper, we conceptually proposed a framework for CDN-like systems which can attached to existing Internet services, operate under pre-set carbon footprint and offset estimated carbon emissions from the traditional Internet services it used. Based on this idea, we designed and implemented a prototype system called GreenMail, which is an IMAP proxy, reducing carbon emission by caching users' email on green hosts. To get a better understanding on our system, especially the cache system behavior, we thoroughly tested the system against both synthetic and real world workloads, estimating the operating cost of our system for 1 year. We also present how to properly estimate carbon emission occurred outside the GreenMail itself.


extfieldsofstudy:
Mathematics
Computer Science

text:
Computing Minimum Tile Sets to Self-Assemble Colors Patterns

Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular color pattern. For $k \ge 1$, $k$-PATS is a variant of PATS that restricts input patterns to those with at most $k$ colors. We prove the {\bf NP}-hardness of 29-PATS, where the best known is that of 60-PATS.

Introduction
Self-assembly, deterministic or otherwise, is a powerful force in nature. Cosmological, biological, and even human sociological systems are all capable of self-assembling with a surprising amount of order on a macro scale, even as the processes used for their construction rely solely on local rules and effects.
We are interested in DNA computation and self-assembly and the tile assembly systems used to model it. Winfree showed that such DNA computation is Turing-universal [13]. A natural question to then ask is, "what is a minimal tile set necessary for performing a certain computation?" Barish et al. [3] have early results for a binary counter. Adleman was the first to also consider the time it takes for self-assembly, and also to ask a related question about minimal tile sets for particular patterns [1].
On self-assembly, Brun has introduced a series of tiling models to perform simple computations like multiplication [2], and to non-deterministically solve NP-Hard problems [4][5][6]. Two main goals are "shape-building" and "pattern-painting." Real world molecules can potentially be designed to deterministically form a specific target shape, as implemented as DNA double-crossover molecules by Winfree [15]. This paper focuses on the self assembly of target color patterns rather than shapes. Various patterns of practical significance were exhibited to self-assemble from DNA tiles, including Sierpinski triangle [10] and binary counter [3]. As illustrated in Fig. 1, blue tile types B1, B2 and red tile types R1, R2 implement a half-subtractor as tile copies self-assemble the binary counter.
Based on the abstract Tile Assembly Model (Winfree again) [14], Ma and Lombardy intro-ducePatterned self-assembly tile set synthesis (PATS) [8]. PATS aims at finding a minimum tile type set with which a rectilinear tile assembly system (RTAS) uniquely self-assembles a given Figure 1: We use four tile types, two colored Red and Blue each, to implement a half-subtractor. For each tile type with glues named (n,s,e,w), we see that its glues perform the operation "west minus south," then pass the output to the east and the carryout to the north. Interpreting Red types as 1 bits and Blue types as 0 bits, with MSBs at the top, we see that the seed's north glues in row 0 interact with this tile type set to successively subtract 1 from one column to the next.
pattern. PATS tries to compute the tile set of minimum size that uniquely self-assembles a given rectangular pattern. The general case, allowing an arbitrary number of colors for the input pattern, was shown to be NP-hard [7].
For k ≥ 1, k-PATS is a PATS' subproblem of practical significance in which inputs are restricted to patterns with at most k colors. Seki proved that 60-PATS is NP-hard [12]. He designed a set T of 84 tile types such it self-assembles a 3SAT evaluator circuit pattern P (φ), which is reduced from a given 3SAT instance φ, if and only if the instance is satisfiable. Gadget (sub-)patterns of P (φ) imply the property that T is the unique smallest tile type set for P (φ) no matter what φ is. Tile types in T implement OR, AND, and NOT gates in order to evaluate φ.
Instead of 3SAT, in this paper we employ SUBSET SUM problem, which can be evaluated using just a half-subtractor similar to Brun [4], and prove the following stronger result.

The Model and Preliminaries
We begin our sufficient description of Rectilinear Tile Assembly System (RTAS) with a proxy for DNA proteins and their "roles," and a method of "attachment." For a formal and excellent introduction, see [11].
A (tile) type is a unit-square with five parameters: four glues g n , g s , g e , g w associated with each edge north, south, east, and west; and a color c. A tile is an instance of a tile type. We assume tiles cannot be rotated or reflected. By inclusion of a particular tile type in a set, we assume that we have access to infinitely many tiles of the type. A color is an attribute of a type that can be shared by multiple types within a set-from a certain DNA perspective, it makes tile types indistinguishable and "serve the same role." A glue is an attribute of a type that is possibly equal to the glues of other types in a set, in which case the glues matchglues will tell us how we can "stick together" tiles.
A (rectangular) assembly (of width w and height h) is a function from a "rectangular" subset {1, ..., w} × {1, ..., h} ⊂ Z 2 + to types such that for any pair of adjacent inputs that share an "edge," the output types' glues on the shared edge are the same. A (rectangular) color pattern (of width w and height h) is a function from a rectangle {1, ..., w} × {1, ..., h} ⊂ Z 2 + to colors. Our model for DNA self-assembly does not take place in a vacuum-we assume the preexistence of an L-shaped seed. Our assembly function maps indexes in the 0-row and 0-column to seed types, which then have exposed north glues and east glues respectively. The seed tiles are colored Slate Gray in all of our graphics. The natural way to understand an assembly is to start with a seed, then the glues work to allow tiles to attach as follows.
A tile can attach at an index (i, j) if and only if both its west glue matches the east glue of a tile already placed at (i − 1, j), and its south glue matches the north glue of a tile placed at (i, j − 1). Therefore an assembly builds up from the south-west seed to the north-east. If an assembly reaches a state such that no more tiles can attach, then it is a terminal assembly.
A Rectilinear TAS is a pair T = (T, σ L ) consisting of a tile type set T and an L-shaped seed σ L . Its size is the cardinality of T . We will use and refer to the requirement that every two tile types must have distinct (south,west) glue-tuples as uniqueness. Two types that violate uniqueness are said to clash.
For RTASs satisfying uniqueness, we see by induction that fixing the exposed seed glues means that a tile placed at an empty index has necessarily deterministic type, and leads to a deterministic terminal assembly. As we care mostly for colors, we will also say it uniquely assembles a color pattern.
As illustrated in Fig. 1, we see that B2 uniquely attaches at index (1, 1) given the exposed seed glues. The three tiles above it are successive copies of tile type R2 and, attaching in turn, none could be replaced by any other tile type. The assembly as shown is terminal. The Pattern self-assembly tile set synthesis (PATS) problem [8,9] asks the question, "given a rectangular color pattern P, what is a RTAS of minimum size that uniquely solves the pattern?" Definition 2 k-colored Pats (k-Pats) Input: a k-colored pattern P; Output: a smallest RTAS which uniquely self-assembles P.
60-PATS was shown to be NP-Hard by Seki [12]. We endeavor to show that 29-PATS is NP-Hard by a polynomial reduction from Subset Sum 1 to the size variant of 29-PATS: given a pattern in 29 colors, what is the minimum size of any RTAS that uniquely self-assembles the given pattern.
For the rest of this paper, we assume we have a black box capable of solving the size variant of 29-PATS.

The Circuit
We reduce an instance SS = (S, n) of Subset Sum to a pattern in 29-colors PATTERN such that 1. there exists a RTAS (T, σ * ) with |T | = 46 that uniquely assembles PATTERN if and only if SS is solvable; 2. there does not exist any tile type set T = T (ignoring isomorphisms) of size 46 or less such that a RTAS (T , σ ) can uniquely self-assemble PATTERN. In this section, we verify (1) for a sub-pattern of PATTERN called CIRCUIT using 26 of the 46 tile types of T . 2 Specifically, we introduce a subset of the critical tile type set T in Fig. 2. An example of the reduction to CIRCUIT is given in Fig. 3. For solvable SS, T can uniquely assemble CIRCUIT, i.e., T is sufficient; therefore, |T | is an upper bound on the output of the black box in these cases. The reduction works as follows: We determine the height of the circuit to be max( log 2 (n + Σ all ) , 21), where Σ all is the sum of all elements in S. 3 Then 2 row# is greater than both n and Σ all . The width of CIRCUIT will be determined online. Then: • The target number n from SS is encoded in binary-MSB at the top-as colors of tiles in the first column, Black for 0 and White for 1. Unique tile types of these colors in T imply that equivalently, n is also encoded in the east glues of this column.
• Using (1 + row#) columns each, we similarly encode elements of S in succession, MSBs on the right. A 0 bit is encoded by a column of colors Right-Arrow Black (RAB), Up-Arrow Black (UAB), and el-Black; a 1 bit by RAW, UAW, and el-White.
• Given our tile type set T and reduction, there are only two colors appearing next to seed tiles in row 1 or column 1 such that the seed has a choice in glues: tile types of colors RAB and RAW have varying south glues. Compare this to the south glues of UAB for example, whose tile types all have south glue 0vp. 2 The other 20 tile types will be necessary and sufficient regardless of the instance SS. 3 Later we add a sub-pattern which requires height of at least 21. Figure 3: For space considerations, and WLOG here, we draw this example with height of 7 rather than 21. SS = (S = {11, 25, 37, 39} , n = 75), the same example as Brun in [4] for easy comparison of the tile sets. S * = {11, 25, 39} so we see the seed north glue of 1* in columns 2, 10 and 26; and seed north glue 1x in column 18.
• Then given T , the set of feasible seeds can only vary in their choice of glues in the first column of the encoding of each element of S; the choice is to "tag" the glue '*' to mean we should subtract the current element, or 'x' to mean we should not.
• The Right-Arrow (RA) and Up-Arrow (UA) tile types cooperate to transfer the subtraction ON/OFF signal through an element's columns until it runs off the top.
• Subtraction of a bit takes place in the RA squares. Tile types below them preserve bit information of the element vertically. If subtraction is ON, the RA tile type works as a halfsubtractor (like in Fig. 1): it receives a "running total" bit from the west, subtracts from it the south bit, outputs to the east and "carries" to the north. If subtraction is OFF, the RA tile type preserves bit information horizontally (passes it through) and carries 0.
• All indexes above the squares colored RAB and RAW are required to be color Carry Blue. These tile types are half-subtractors again, to complete the carry operation correctly from column to column.

Figure 4:
We add these 20 tile types to our set T . While they are not necessary to uniquely assemble CIRCUIT, adding them does not affect the sufficiency of T , now of size 46; they will be used in auxiliary patterns that will be attached to CIRCUIT such that all 46 tiles are necessary.
• Below the RA colors, subtraction has already taken place so bit information is preserved horizontally for use by the next element of S to the right.
• The last column of CIRCUIT is all Black. We started with t, we subtracted some subset of elements of S. For an instance of SS for which S * exists, we should finish with all-Black 0.
Proposition 3 Given an SS and our tile type set T , the RTAS (T, σ * ) with |T | = 26 uniquely assembles CIRCUIT if and only if SS is solvable.
Proof The reduction correctly encodes n and the elements of S, and correctly does subtraction or not. The proof is in the previous analysis, for further justification see Brun [4]. Then our choice over feasible seed glues is exactly equivalent to choices over subsets S ⊆ S of elements to subtract from n to try to obtain 0. •

Minimum Tile Complexity
In the last section, we described a tile type set T and showed that it is sufficient to self-assemble the color pattern CIRCUIT that results from reducing any satisfiable instance of Subset Sum, given an appropriate seed σ * . At this point, the size of T is an upper bound on what the black box can return on a satisfiable input CIRCUIT. But in a trivial example in which the elements of S sum to n exactly, we have no use for any tile types utilizing the glues 0x or 1x so output will be less. Worse, it is possible that given an unsolvable instance, the black box outputs 26 or less using some other T , making it indistinguishable from a solvable instance of subset sum.
So we have a need to establish a lower bound on the output from the black box for any input. To do this, we add the tile types in Fig. 4 to T .
We will join CIRCUIT with auxiliary patterns into the full input PATTERN; then for each color c that appears in PATTERN, we will prove that the number of tile types colored c needed by any set Figure 5: LB1 is presented sideways for space considerations. The Slate seed tiles should be interpreted as being the 0-row, then it is the rows that are numbered up to its height of 21. LB1 guarantees that there are at least 2 tile types colored each of el-Black, el-White, and Carry Blue.
T that uniquely assembles PATTERN must be at least the number used by T of color c. Finally, summing over types will give us our lower bound-the black box cannot output less than 46. Auxiliary patterns must meet the following constraints: they must assemble using T , i.e., be consistent; they must also "splice" together using T . Failing either, we lose the sufficiency of T . However, these constraints do endow a benefit: because T is sufficient to assemble CIRCUIT and all auxiliary patterns for reductions from satisfiable instances of Subset Sum, we know for these cases that the black box need not consider tile type sets larger than 46.
So the goal of this section and the next is to design auxiliary sub-patterns such that, including them in PATTERN, the tile set T will be necessary. Sub-patterns in this section are named LB# for Lower Bound. We claim that T is sufficient for all auxiliary patterns in Sections 4 and 5 without proof. The strategy for joining together the various sub-patterns is given as part of correctness in Section 6.
We take it as a given that the 29 colors described in T will be used in some sub-pattern of PATTERN. There are 22 colors in PATTERN with just one tile type of their color in T . 4 Each trivially requires one type, so we have finished 22 of our 29 necessary lower bound proofs, leaving 17 tiles unassigned, or free.
Sub-pattern LB1 is given in Fig. 5 and is used in the next result.
Proposition 4 If LB1 appears as a sub-pattern of PATTERN, then in any minimum tile type set solving PATTERN, either there must be at least 2 tile types with distinct east glues of each color el-Black, el-White, and Carry Blue as we suggest in T ; or the black box must find a minimum tile type set larger than 46.
Proof By symmetry, we only need to prove the case for el-Black. We assume that the black box can find a solution using at most 46 tile types. By contradiction, assume there is only one tile type el-Black. Then there is only one glue east of column 2, call it e. The Black types can have at most 18 unique north glues in column 3, so by the 19th north glue, they must cycle (because the west glue is a constant). But this requires a Black tile at (3,20), not White. • Figure 6: LB0 is presented sideways to conserve space. Looking at it from the side, variables on the left are row indexes, with i at the bottom. There are two alternating glue names between the second and third columns, e and e . Above the vertical ellipsis, they are represented by and , such that they still alternate, but whether e is equal to or depends on the parity of the number of rows. It is also possible that there is only one glue. (Then e is equal to e is equal to is equal to .) In either case, given enough consecutive rows of Black tiles, new Black types must eventually be exhausted and the vertical glues in the third column must "cycle." Then the White tile at (3, k + 1) must clash with a Black type, so there must actually be at least two types of the variable Yellow color with distinct east glues. As a final note, the seed is not necessarily present-we can start in row i.
Proposition 4 gave us 2 tile types for Blue Carry tiles, but we need a lower bound of 4. We will obtain it in Proposition 11, first we need the next lemmas.
Proposition 4 also assigned 3 of our free tile types. Now of 46 types from our upper bound, we have assigned 32, leaving 14 free.
We start by generalizing the result in Proposition 4, using LB0 in Lemma 5.
Lemma 5 If LB0 appears as a sub-pattern of PATTERN, such that starting in row i, there are (k − i + 1) consecutive rows of Black-Yellow-Black as shown such that the east glues of the second column are either all the same or alternate between two glues, and the row (k + 1) continues the glue pattern but requires White tiles in the first and third columns, and such that (k − i) is at least the maximum number of Black types, then in any minimum tile type set solving PATTERN, either the Yellow tile in row (k + 1) must have an east glue distinct from e and e , and therefore be a different type than any appearing below it; or the black box must find a minimum tile type set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types. Then by contradiction, assume that we can place a Yellow tile at (2, k + 1) that has east glue . In two cases. First, assume the east glue of every tile in column 2 is known to be the same, e. Assume M is the Minimum Tile Type Set found by the black box. Now consider the subset Be ⊂ M to be the subset restricted to only types colored Black with west glues e. These are the candidate types whose tiles can be placed in the third column. Reduce Be to a directed graph G where each type x is represented by a node with out-degree at most 1: each node v x points to the node of the type in Be whose south glue is equal to x's north glue, if such a type exists. 5 Now for any tile type y ∈ Be placed at the "bottom" index (3, i) of LB1, it must be that the type placed directly north of it can be determined by following the edge out of y's node in G, as this neighbor of y must have west glue e (by its inclusion in Be), and south glue equal to y's north glue (by design of the edge).
This logic repeats as we move north placing tile types in the third column in LB1, and we see that the order of types placed is determined by following out-edges in G.
However, the black box can assign the color Black to at most (k − i) types. Then we know that for any starting node in G (and corresponding type placed at (3, i)), after (k − i) hops we must be in some cycle of G. Why? Because there can be at most (k − i) unique north glues, therefore the (k − i + 1)th north glue must repeat. This cycle corresponds to a cycle of vertical glue names. 6 Further, as we continue to place types moving north, uniqueness requires that we stay in this cycle as long as the west glues of the types must be e. But then the type at (3, k) must be Black, not White, giving us our contradiction.
In the case that there are two alternating east glues in column 2, we call them e and e , and the proof proceeds much the same.
Be now contains Black types with west glue either e or e . The reduction is to a bipartite graph BG (one partition for types with each west glue), where each type x has a node v x with out-degree at most 1, and points to the node of the type y such that y 's west glue is different than x 's (because the glues alternate) and y 's south glue is equal to x 's north glue. Then again edges represent "stack-ability" in column 3. And again, there are at most (k − i) nodes, so after starting by placing any type in (3, i) and making (k − i) hops, we are in a cycle. This cycle guarantees that the north glue at index (3, k), combined with glue , is known to require placing a Black type at (3, k + 1). This contradiction completes the second case. Lemma 6 If LB1 appears as a sub-pattern of PATTERN, then in any minimum tile type set solving PATTERN, either it is true that if there are exactly 2 Blue Carry tile types, then the north and south glues of both types must all be the same glue; or the black box must find a minimum tile type set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types. From Proposition 4 we can assume that the 2 Carry types have distinct east glues. All cases use LB1. Case 1. Neither type self-stacks vertically. 7 In this case the types must alternate verticallyif they do not, then combined with neither type self-stacking, it will not be possible to place types in more than the first two rows of LB1 column 6. However if their north and south glues do allow them to alternate, then we can apply Lemma 5 to see that we need a type at (6,20) with an east glue unique from both types that we have, completing this case. Case 2a. Exactly one type x self-stacks vertically, and x is placed at (6, 1) of LB1. In this case, Lemma 5 can force our non-self-stacking type y, to be placed at (6,20), if not at a smaller row-index in column 6. This implies that y's south glue equals the north-and-south glue of x. But then neither type can place at index (6, 21) (or at some other index directly above y if it is used earlier), as x and y have the same south glues, while y's north glue is distinct. Case 2b. Exactly one type x self-stacks vertically, but y is placed at (6, 1). In this case y doesn't self-stack so we must place x at (6,2). Indeed, we must place x at every remaining index of column 6, as neither type can have south glue equal to y's north glue. Then there are 18 consecutive rows of Black-Blue-Black with one critical glue between the second and third columns and 14 free tiles, so by Lemma 5, the type at (6, 20) must have a different east glue than the consecutive types before it. But there is only one other type we can place here, y, whose south glue does not match, giving us the contradiction. Figure 7: It should be understood that the sub-patterns that appear above the ellipsis in LB2 through LB5 will be appear as the top rows when placed within PATTERN. These color sub-patterns are the result of subtracting 0 (all element bits 0) in LB2 and LB3 and 2 row# in LB4 and LB5 (all element bits 0 except the MSB is 1) from the "numbers" given in the respective first columns. Case 3. Both types self-stack, but do not stack with each other. In this case, regardless of which type we place at (6, 1), it can only stack with itself all the way up to row 19. But again we can apply Lemma 5 to force (6,20) to be a distinct type, which is impossible because the second's south glue does not equal the north glue of the first. The only remaining possibility is that both Carry Blue types self-stack, and stack with each other, which is our desired result. • We make a slight detour from the Carry Blue lower bound and turn our attention to sub-patterns that include the UAB, UAW, RAB, and RAW tiles. We prove preliminary results now, and return to some of these sub-patterns later. Obtaining the results in this order allows us to "save" colors.
We present sub-patterns LB2 through LB5 for Lemma 7 in Fig. 7.

Lemma 7
If LB2 through LB5 appears as a sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, we must have at least 2 types colored UAB or at least 2 types colored Black; and at least 2 types colored UAW or at least 2 types colored White.
Proof By symmetry, we only prove the case for UAB and Black. By contradiction, assume there is only one tile type colored UAB with east glue e, and one tile type colored Black with north glue n. Then for both LB2 and LB3, the tile placed at their respective (6,4) indexes must have west glue e and south glue n. But by uniqueness, it is impossible for two different tiles to do this, one colored Black as needed by LB2 and one colored White as needed by LB3. • In Lemma 8 we obtain a result for RAB and RAW similar to Lemma 7, again to save colors. We present sub-patterns LB6 and LB15 in Fig. 8, and LB24, and LB33 in Fig. 9, for the results in Lemma 8 and Lemma 9.
It should be understood that there are 9 total copies of each sub-pattern, one for each color "value" that the variable-Yellow indexes should take. For example, the patterns LB6 through LB14 are given at the top of Fig. 8 with variable-Yellow replaced by Black and each of P1 through P8 respectively. These 36 sub-patterns will be used again in Proposition 12 to obtain a lower bound of 4 for RAB and RAW.
Of 46 tile types, we have assigned 32; 1 more is known to be UAB or Black; another 1 more is known to be UAW or White; 12 are free to be any color.

Lemma 8
If LB1 through LB41 appear as sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, either we must have at least 2 types colored RAB and at least 2 types colored RAW as we suggest in T ; or the black box must find a minimum tile type set larger than 46.
Proof We prove the implied lower bound for RAB, then RAW by symmetry. We assume the black box can find a solution using at most 46 tile types. By contradiction, assume there is only one tile type colored RAB. Then uniqueness requires that there must be four distinct tile types, one with each of the four Green colors, with distinct south glues. Four distinct south glues at the indexes colored G1, ..., G4 in LB6 through LB23 would require 24 free tile types for the various Purple colors. But we only have 12 types free to be any Purple color. • We also get the following result from LB6 through LB41.

Lemma 9
If LB6 through LB41 appear as sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, either it must be true that if the number of free tile types remaining is insufficient to allow for there to be two types of each of the 9 yellow-Variable colors, then there are at least 4 tile types with distinct east glues colored RAB and at least 4 tile types with distinct east glues colored RAW; or the black box must find a minimum tile type set larger than 46.
Proof We prove the implied lower bound for RAB, then RAW by symmetry. We assume the black box can find a solution using at most 46 tile types.
From the Lemma statement, we can also assume that there are not enough free tile types to assign them colors Black and the Purple colors P1, ..., P8 such that each of these 9 colors has at least 2 tile types assigned to its color. Therefore there must be a color in this set such that there is only one type of its color, call it C; and the unique type colored C has north glue n. Now we analyze in the two sub-patterns described in Fig. 8 corresponding to variable-Yellow taking the color C. We see that n must be the south glue of at least one type colored by each of the 4 Green colors. By uniqueness, these 4 distinct types colored G1, G2, G3, and G4 must have distinct west glues given their common south glue n. This would require at least 4 tile types colored RAB with distinct east glues. • We need sub-pattern LB42 in Fig. 10 and one more lemma before proving a minimum of 4 tile types colored Carry Blue. Lemma 10 is technical and three pages long, and can be skipped.
Lemma 10 If LB42 appears as a sub-pattern of PATTERN, along with LB1, then in any minimum tile type set solving PATTERN, either it must be true that if there are less than 4 Blue Carry tile types, then there must be at least 4 tile types colored Black or White combined; or the black box must find a minimum tile set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types, then we do a case analysis. From Proposition 4 we know that there must be at least 2 Carry types. And of course we must have at least 1 Black and 1 White type, 2 total. So we consider the following six possible combinations and show them all to be impossible: there are either 2 or 3 Carry types; and there are either 1 Black and 1 White, or 1 Black and 2 White types, or 2 Black and 1 White. Cases 1&2. 2 or 3 Carry types, 1 Black, 1 White. Because of the Black and White subpatterns that appear in columns 3 and 4 of LB42, we know that the unique Black and White types can be said to have the glues we suggest in T . 8 Then the horizontal glues of the Black and White types are distinct, which means that we need at least 4 distinct Carry tile types to place at (5, 2), (5, 3), (7,2), and (7, 3), because these indexes require distinct (east,west) glue pairs.
For the more complicated remaining cases, we use the following naming conventions for the types, to the extent that they exist in the Case: Black types are B1 and B2; White types are W1 and W2; Carry types are C1, C2 and C3. When appropriate, as a convenience for both us and the reader, we will assign glue names to these types as to keep them consistent with T . Case 3. 2 Carry types, 2 Black, 1 White. There is only 1 White tile type W1, and it stacks with itself both vertically and horizontally, so WLOG we can fix its glue names as suggested in T . So W1's (n,s,e,w) is (#,#,1h,1h). Now we know that there must exist a Carry type with east and west glue both 1h from index (5, 3) of LB42 between two White tiles, so we assign these glues to C2.
Also we see that the Black tile at (8, 3) has White tiles above and below it, so we can say the type placed here is B1 and has north and south glues #. Also it must now have a west glue unique from W1's, or it will violate uniqueness. So we can call its west glue 0h. Now the tile at (7, 3) has east glue 0h. Type C2 has already been assigned east glue 1h, so we must place C1 at (7,3). We also see that from a White tile at (6,3), this index, and therefore type C1, must have west glue 1h.
But now by Lemma 6, we know that if there are only two Carry tile types, they must have all four of their north and south glues the same, call it g. But now types C1 and C2 have the same (south,west) glue pair (g,1h), violating uniqueness. Case 4. 2 Carry types, 1 Black, 2 White. There is only 1 Black type B1, and it stacks with itself both vertically and horizontally, so we can fix its glue names as suggested in T . So B1's (n,s,e,w) is (#,#,0h,0h). Now we know that there must exist a Carry type with east and west glue both 0h from index (5, 1) of LB42 between two Black tiles, so we assign these glues to type C1.
Also we see that the White tile at (10, 4) has Black tiles above and below it, so we can say the tile placed here is type W1 and has north and south glues #. Also it must now have a west glue unique from B1's, or it will violate uniqueness. So we can call its west glue 1h.
Then the Carry tile at (9, 4) must have east glue 1h and be type C2, as C1 has already been assigned east glue 0h. Now. Neither the tile at (8, 1) nor the tile at (8, 2) can be type W1. Otherwise (7, 1) or (7, 2) has east glue 1h, which makes one of them type C2, as C1 is known to have east glue 0h. But then C2 has west glue 0h, and as in the last Case, by Lemma 6 both types must have south glue g, so C1 and C2 have identical (south,west) glue pairs, (g,0h), violating uniqueness.
So instead tiles at both (8, 1) and (8, 2) must be type W2. Then W2 both self-stacks vertically and has north glue at (8,2) equal to B1's south glue #, so W2's south glue must be # as well. We must place C1 known to have east glue 0h, or C2 known to have east glue 1h, at (7, 1), because we only have two Carry tiles. But either east glue when it becomes the west glue of W2, will cause W2 to clash with either the (south,west) glue pair of B1 (#,0h), or W1 (#,1h), giving us our contradiction. Case 5. 3 Carry types, 1 Black, 2 White. We start the same as case 4. There is 1 Black type B1 with glues (n,s,e,w) equal to (#,#,0h,0h). WLOG we will say that a type C1 is placed at (5, 1) and has east and west glues 0h. From (10, 4), we can say that type W1 has north and south glue #, and then must have west glue distinct from 0h, so call it 1h. The tile at (9, 4) has east glue 1h, so we can say that it is C2. Now we try to rule out the possibility that C3 has east glue 0h or 1h. By contradiction, assume that it does. Then every Carry type has east glue 0h or 1h. As a result, W2 must have a south glue distinct from #. To see this, we realize that W2 must be used somewhere in LB42 other than the first column. 9 If all Carry tile east glues are 0h or 1h, the west glue of W2 must be 0h or 1h. Then a W2 # south glue would clash with either B1 or W1, so instead it must be different.
Then W2 can only appear in the first row. Its distinct south glue means it can not be placed above the # north glue of B1 and W1, and it cannot self-stack, or else its distinct north glue at (8,2) or (10, 2) would fail to match the south glues of B1 that appear in those columns in row 3.
Therefore every White tile not in row 1 must be type W1. From (3, 3) and (4, 3) we see that W1 stacks horizontally with itself, so its east glue must be equal to its known 1h west glue. We also previously said that the tile at (9, 4) is C2. We now know that, like its 1h east glue, it has west glue 1h from W1 at (8,4).
At this point, assume C3 has east glue 1h. Then no Carry tile can be placed at (7,3). C1 has west glue 0h which fails to match the east glue of W1 at (6, 3); C2 and C3 have east glue 1h which fail to match the west glue of B1 at (8,3).
Alternatively assume C3 has east glue 0h. Then no Carry tile can be places at (7,2). C1 and C3 have east glue 0h which fails to match the west glue of W1 at (8,2). C2 has west glue 1h which fails to match the east glue of B1 at (6,2).
So it must be that the east glue of C3 is distinctly 2h. C3 must be used or the proof against Case 4 goes through. So with B1 and W1 west glues already assigned, it must be W2 that has west glue 2h.
We also realize that it must be C1 placed to the left of every Black tile, as the three Carry tile east glues are all distinct. Then we know C1 self-stacks vertically at (2, 1) and (2, 2), so we can say it has north and south glue g. We also see that the tile at (9,4), previously decided to be C2, has C1 to its north and south. Therefore its north and south glues must also be g. Now we must place C3 at (7, 2). C1 cannot be placed there because its 0h east glue cannot match the 1h or 2h west glues of the White types. C2 cannot be placed there because then it would have a 0h west glue, and its (south,west) glue pair of (g,0h) would clash with C1.
Then what is the south glue of C3? By placing C3 at (7, 2), it has west glue 0h, so it cannot also have south glue g, or it would clash with C1. So it has distinct south glue g2. Neither C1 nor C2 has north glue g2, so C3 must also be placed at (7, 1), implying that C3 self-stacks and its north glue is also g2. But then no tile can be placed at (7,3). The g south glue of C1 and C2 does not match the north glue of C3; and the 2h east glue of C3 does not match the 0h west glue of B1 at (8, 3), and we have reached our contradiction. Case 6. 3 Carry types, 2 Black, 1 White. This case proceeds similarly to Case 5.
This time we start the same as Case 3. There is 1 White type W1 with glues (n,s,e,w) equal to (#,#,1h,1h). We will say C2 is the type at (9, 4) and has east and west glues 1h. From (10, 3), we can say that type B1 has north and south glue #, and then must have west glue distinct from 1h, so call it 0h. The tile at (9, 3) has east glue 0h, so we can say that it is type C1. Now we try to rule out the possibility that C3 has east glue 0h or 1h. By contradiction, assume that it does. Then every Carry tile has east glue 0h or 1h. As a result, B2 must have a south glue distinct from #. To see this, we realize that B2 must be used somewhere in LB42 other than the first column. If all Carry tile east glues are 0h or 1h, the west glue of B2 must be 0h or 1h. Then a B2 # south glue would clash with either B1 or W1, so instead it must be different.
Then B2 can only appear in the first row. Its distinct south glue means it can not be placed above the # north glue of B1 and W1, and it cannot self-stack, or else the distinct north glue at (3, 2), (4, 2), or (6, 2) would fail to match the south glues of W1 that appear in those columns in row 3.
Therefore every Black tile not in row 1 must be type B1. From (3, 2) and (4, 2) we see that B1 stacks horizontally with itself, so its east glue must be equal to its known 0h west glue. We also previously said that the tile at (9, 3) is C1. We now know that, like its 0h east glue, it has west glue 0h from B1 at (8,3).
At this point, assume C3 has east glue 1h. Then no Carry tile can be placed at (7,3). C1 has west glue 0h which fails to match the east glue of W1 at (6, 3); C2 and C3 have east glue 1h which fail to match the west glue of B1 at (8,3).
Alternatively assume C3 has east glue 0h. Then no Carry tile can be places at (7,2). C1 and C3 have east glue 0h which fails to match the west glue of W1 at (8,2). C2 has west glue 1h which fails to match the east glue of B1 at (6,2).
So the east glue of C3 is distinctly 2h. C3 must be used or the proof against Case 3 goes through. So with B1 and W1 west glues already assigned, it must be B2 that has west glue 2h. We also realize that it must be C2 placed to the left of every White tile, as the three Carry tile east glues are all distinct. Then we know C2 self-stacks vertically at (2, 3) and (2, 4), so we can say it has north and south glue g. We also see that the tile at (9,3), previously decided to be C1, has C2 to its north and south. Therefore its north and south glues must also be g. Now we must place C3 at (7,3). C2 cannot be placed there because its 1h east glue cannot match the 0h or 2h west glues of the Black tiles. C1 cannot be placed there because then it would have a 1h west glue, and its (south,west) glue pair of (g,1h) would clash with C2.
But then what is the south glue of C3? By placing C3 at (7,3), it has west glue 1h, so it cannot also have south glue g, by uniqueness. So it has distinct south glue g2. Neither C1 nor C2 has north glue g2, so C3 must also be placed at (7,2). But then its east glue of 2h clashes with the 1h west glue needed by (8,2), and we have reached a final contradiction. • With LB42 and Lemma 10, we have shown that if we insist on using less than 4 tile types colored Carry Blue, we must pay a price by adding at least two tile types colored Black or White. We now leverage this result by adding copies of the colors Black and White, and copies of LB42 as sub-patterns LB43 through LB46.
Of 46 tile types, we have assigned 34; 1 more is known to be UAB or Black; another 1 more is known to be UAW or White; 10 are free to be any color.

Proposition 11
If LB42 through LB46 appear as sub-patterns of PATTERN, along with LB1 through LB41, then in any minimum tile type set solving PATTERN, either there must be at least 4 Carry tile types colored Blue as we suggest in T ; or the black box must find a minimum tile type set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types. Now by contradiction, assume that it can do so using fewer than 4 Carry Blue types.
Then from Lemma 10, we know that it must use at least 4 total tile types colored Black and White. But by symmetry, Lemma 10 would apply to each pair of colors Black1 and White1 through Black4 and White4 as well, because we include auxiliary patterns LB43 through LB46. Then we must also use at least 4 total types of each of the 4 pairs of Black and White copies. Between the original sub-pattern LB42 and its 4 copies, this will require us to use at least 10 additional free tile types, two of which can be the types that are "unknown but restricted" to two colors. This leaves 2 types free. Now we return to LB6 through LB41 in Fig. 8 and Fig. 9. RAB and RAW already have lower bounds of 2 types each. With 2 free types remaining available to us, we see that either RAB or RAW must have a maximum of 3 types assigned its color.
But with at most 2 free types that can be assigned to the Purple colors P1, ..., P8, the conditions are in place to apply Lemma 9, which would require us to have at least 4 types colored RAB and at least 4 more types colored RAW. This contradiction shows that we must use at least 4 Carry Blue types, or increase the size of the tile type set. • We have reached the following state: of 46 tile types, we have assigned 36; 1 more is known to be UAB or Black; another 1 more is known to be UAW or White; 8 are free to be any color. With only 8 free types left to take the colors Black or P1, ..., P8, we are in a position to prove the lower bounds of 4 for both RAB and RAW. To do so we will also need sub-patterns LB47 through LB82 in Fig. 12.

Proposition 12
If LB1 through LB82 appear as sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, either there must be at least 4 tile types colored RAB with distinct east glues, and at least 4 tile types colored RAW with distinct east glues, as we suggest in T ; or the black box must find a minimum tile type set larger than 46.
Proof By symmetry we only prove the case for RAB. We assume that the black box can find a solution using at most 46 tile types. The current lower bound for every color Black, P1, ..., P8 is 1 tile. There are 9 total tile types available to be assigned these colors-one is restricted to be Black or UAB, and 8 more free.
Therefore if we do not assign all 9 of these tile types to be second types of colors Black, P1, ..., P8, then Lemma 9 would be immediately applicable to give us the desired result. So assume these previously unassigned types are colored as necessary to maintain a contradiction of the stated result.
Now there are no more free tile types, except one type restricted to be White or UAW. Therefore there is only one tile type of each of the colors UAB, G1, G2, G3, and G4. Consider the unique tile type colored UAB and call its west glue e1 as labeled in Fig. 12.
By the uniqueness of types of the listed colors, this must be the east glue of every type colored Green. We also see that for colors G1 through G4, the unique tile type of each color self-stacks horizontally in LB47 through LB82. Therefore each of these tile types also has west glue e1.
If all four tile types colored G1 through G4 have west glue e1, then uniqueness requires that they have distinct south glues. This would in turn require at least four tile types of each Purple color, which is impossible-there are theoretically two tile types of each Purple color and we have zero free types remaining. Having reached a contradiction, we can apply Lemma 9 directly. • Proposition 13 proves the lower bound of 4 for each of the colors UAB and UAW, the last lower bound proofs needed for Section 4. It uses LB47 through LB82 in Fig. 12 again for UAB, and LB83 through LB118 shown in Fig. 13 and Fig. 14 for the symmetrical argument for UAW.
It should be understood that there are 18 copies of LB47, one for each combination of: '1?2' equal to G1 or G2, and variable-Yellow assigned each of its 9 possible colors. For instance, we say that LB47 is the copy with color G1 appearing in indexes (5, 2) through (10, 2), and color Black in indexes (5, 1) through (10, 1). And similarly there are 18 copies of LB65. Then there are 9 copies of each UAW sub-pattern LB83, LB92, LB101, and LB110.
Of 46 tiles, we have assigned 40; 1 more is known to be UAB or Black; another 1 more is known to be UAW or White; 4 are free to be any color.

Proposition 13
If LB47 through LB118 appear as sub-patterns of PATTERN, along with LB1 through LB46, then in any minimum tile type set solving PATTERN, either there must be at least 4 tile types colored UAB with distinct west glues and at least 4 tile types colored UAW with distinct west glues as we suggest in T ; or the black box must find a minimum tile type set larger than 46.
Proof By symmetry we only prove the case for UAB, the UAW proof is the same using the subpatterns in Fig. 13 and Fig. 14 and the remaining free tile types after the proof of the UAB lower bound. We assume that the black box can find a solution using at most 46 tile types.
Because we only have 4 free types left that can be any of the 9 variable-Yellow colors, there must be at least one color in the set such that there is only 1 tile type of that color. Call it C, and we analyze the four sub-patterns in which C appears. Also, to assist clarity in this proof, some glue labels that appear in our analysis are shown in Fig. 12. Figure 13: LB83 through LB100 present half of the sub-patterns for UAW that are analogous to those for UAB in Fig. 12. The other half are in Fig. 14. The sub-patterns are presented 18 at a time for UAB and 9 at a time for UAW because the roles of the different tile types in subtraction require more arrangements of the colors Black and White in the first, third, and last columns across the various pattern designs for UAW than for UAB. Say the unique tile type colored C has north glue g * . Now for each Green color G1, G2, G3, G4, there is a sub-pattern where it self-stacks horizontally such that it appears in 6 consecutive indexes, each above a tile colored C. We now proceed similarly to the proof of Lemma 5.
Consider G1. Because we only have 4 free tile types left that can take the Green colors, we know that there can be at most 5 types colored R1 with south glue g * , with at most 5 distinct east glues.
Because we have 6 consecutive indexes colored R1 such that each must have a tile with south glue g * placed in it, it must be the case that the 6th tile colored R1 placed at index (10, 2) has an east glue e1 that is a repeat of the east glue of one of the tiles colored R1 somewhere to its left. WLOG say it is the same as the east glue of (6, 2) as shown in Fig. 12.
We do the same analysis for the three other sub-patterns with C in row 1 and respectively each of R2, R3, and R4 in row 2. Specifically, the respective east glues e2, e3, e4 of their tiles at (10, 2) must each be copies of the east glue of a tile of the same color that is placed farther left. Again, WLOG, the tiles at (10,2) can all be copies of the tiles at (6, 2) of their respective sub-patterns. Now consider the indexes (7, 2) of the 4 sub-patterns with C in row 1. A tile placed in each sub-pattern at (7, 2) must have the same south glue g * , and has a Green color distinct from the Figure 14: The other half of the UAW patterns, referenced in Fig. 13. The colors represented by variable-Yellow are shown here reflect all 72 sub-patterns including those in Fig. 12 and Fig. 13.
others, so they must be different tile types. Then uniqueness requires that the west glues of the tiles placed at (7,2) in each sub-pattern must be distinct. But the west glues of these tiles are exactly e1, e2, e3, e4, so these 4 glues must be distinct.
Finally, we see that going back to e1, e2, e3, e4 as the east glues of the G1, G2, G3, G4 tiles placed at index (10,2) in each of the 4 sub-patterns, that they must be 4 distinct west glues of tile types colored UAB. • Of 46 tile types, we have assigned all 46, allowing Proposition 14.

Proposition 14
If LB1 through LB118 appear as sub-patterns of PATTERN, then for any minimum tile type set solving PATTERN, it must have total size at least 46, with the desired lower bounds holding for each color respectively, as we suggest in T .
Proof Aggregating the results in this Section 4 have established the desired lower bound for each color. Summing over colors gives the overall lower bound of 46. •

Glue Interpretations
In this section, we show that if T has size 46, then the glues of some tile types in T must be isomorphic to the names we give to them in Fig. 2. It will be sufficient to only prove the glue scheme for tile types used in CIRCUIT 10 because then it is clear that unsolvable SS cannot solve CIRCUIT in 26 tile types. For convenience, and WLOG, we use the type-naming and glue-naming schemes in T . New patterns are named GE#, for Glue Enforcement.
We re-use LB42 in Fig. 10 on page 13 for the next two propositions.

Proposition 15
If LB1 through LB118 appear as sub-patterns of PATTERN (and establish a minimum tile type set size of 46), then in any minimum tile type set solving PATTERN, either the glues of the Black and White tile types are as we suggest in T ; or the black box must find a minimum tile set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types. Then there must be exactly 1 type of each color Black and White, as we exhaust 46 tile types to satisfy all lower bounds established in Section 4. Now we see in LB42 that BLACK self-stacks both vertically and horizontally, therefore we know that it has the same north and south glues, call it #, and the same east and west glues, call it 0h. 11 WHITE stacks both above and below BLACK, so its vertical glues are the same.
WHITE also self-stacks horizontally, so it also has its east glue equal to its west glue, call it 1h. However by uniqueness, the glues 1h and 0h must be distinct, because of the common # south glues of the tile types. • Proposition 16 If LB1 through LB118 appear as sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, either the glues of the Carry Blue tile types are as we suggest in T ; or the black box must find a minimum tile set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types. Then there must be exactly 4 tile types of color Blue, as we exhaust 46 tile types to satisfy all lower bounds established in the last section. Now using Proposition 15 we see in LB42 that four Blue tile types necessarily have (east,west) glue pairs known to be distinct. For example, tiles placed at indexes (2, 2), (7,2), (2,3), and (7,3) require their glues to be (0h,0h), (0h,1h), (1h,1h), and (1h,0h) respectively. This exhausts the Blue types available. Name the distinct types that end up at these indexes CA1 through CA4 in order.
We notice that CA1 stacks with itself at (2, 1) and (2, 2) (because we have shown that Carry tile types are identifiable by their west-east glue pairs), and CA3 stacks with itself at (2,3) and (2,4), and they stack both above and below each other. Therefore the north and south glues of both types must all be equal, call it 0vc. 12 Note that this glue 0vc must also be present between (7,3) and (7,4), so it is also the north glue of CA4.
Now we look at CA2 and notice that it stacks with itself at (7, 1) and (7,2). Therefore its north and south glues must be equal; and additionally they must be the same as the south glue of CA4. However, they cannot be 0vc, otherwise the CA2 tile attaching at (7, 2) would not do so uniquely (it would clash with CA1 at (3,2)). So this second group of glue assignments must be distinct, call it 1vc. Neither 0vc nor 1vc can be the same as #, by uniqueness. • Propositions 15 and 16 have established that all tile types of colors Black, White, and Carry Blue must have glue names matching those we assign in T (gnoring isomorphisms) for all tile sets able to self-assemble CIRCUIT. The next step is to obtain the same result for el-Black and el-White.
Proposition 17 If LB1 through LB118 appear as sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, either the glues of the el-Black and el-White tile types are as we suggest in T ; or the black box must find a minimum tile type set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types. Then there must be exactly 2 tile types of each color el-Black and el-White, as we need 46 types to satisfy all lower bounds established by Section 4. We name the types as in T . We only prove the el-Black case, the el-White case is symmetric.
Now we see in LB1 (Fig. 5, page 7) that the two el-BLACK types necessarily have known (east,west) glue pairs equal to (0h,0h) and (1h,1h) from the known horizontal glues of Black and White neighbors. Further, el-BLACK1 tiles are placed both above and below a tile colored el-BLACK0, which self-stacks vertically, so all of their vertical glues must be the same, call it 0vp.
In the symmetrical case, call the vertical glue of the el-White types 1vp. 0vp and 1vp must be distinct from #, 0vc, and 1vc, by uniqueness. • The last goal is to prove that the glue schemes of the RA and UA tiles must match the names in T . The next two results make it much more straightforward. Now that we have Proposition 17 proving the glues for the el-Black and el-White tile types, we can prove the following Lemma describing their behavior as horizontal "pass-throughs." Lemma 18 If LB1 through LB118 appear as sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, either it is true that for any number k ≥ 1 of tiles colored el-Black and el-White placed consecutively in a horizontal row, the east glue of the eastern most tile and the west glue of the western most tile must be the same; or the black box must find a minimum tile type set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types. Then by Proposition 17, the tiles colored el-Black and el-White are correctly described in T . A quick check shows us that every tile of these colors "preserves" glues horizontally, i.e., has the same east and west glues. A trivial induction gives the result. • We can now claim that horizontal glues are the same on both sides of an ellipsis in a sub-pattern if it is implied that all hidden tiles are el-Black or el-White. Proving the glues of the Green tiles is the next supporting step.

Proposition 19
If LB1 through LB118 appear as sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, either the glues of the tile types of Green colors G1, G2, G3, G4 are as we suggest in T ; or the black box must find a minimum tile type set larger than 46.
Proof We assume that the black box can find a solution using at most 46 tile types. Then there must be exactly 1 type of each of the four Green colors G1, G2, G3, G4, as we need 46 types to satisfy all lower bounds. We name the types as in T .
Consider LB6 and LB15 in Fig. 8. Because Black is one of the variable-Yellow colors, we can see that the unique tile type of each Green color stacks both above and below Black's unique tile type and its # north and south vertical glues. Therefore every Green type must have north and south glue #. Figure 15: After Proposition 20, the glue names appearing above are necessary for tile type sets T of size 46 that solve our reduction PATTERN.
Then in LB47 and LB65 in Fig. 12, we can see that each of the four types stacks horizontally with itself, so each has east glue equal to west glue. However, we also know from Proposition 14 that their west glues are all distinct. Uniqueness also requires that they are all distinct from 0h and 1h, the only other two horizontal glues we have identified so far. Therefore we can give to them the distinct names as in T . • With Lemma 18 and Proposition 19 in place, we can get one more result using the LB# patterns before we need new sub-patterns to finish. Now Proposition 20 should be intuitive here because we can look at the RA and UA tiles in the second row of the necessary sub-patterns and see that recent results tell us the exact tiles placed at three of the neighboring indexes.
Proposition 20 If LB1 through LB118 appear as sub-patterns of PATTERN, then in any minimum tile type set solving PATTERN, either the (south,east,west) glues of all UAB and UAW tile types, and the (north,east,west) glues of all RAB and RAW tile types, are as we suggest in T ; or the black box must find a minimum tile type set larger than 46. Figure 16: Green colors G1 and G3 are associated with subtraction ON signal. In, sub-patterns GE1, GE2 and GE3, we can identify RAB and UAB types by their neighbors, and force the vertical glue name 0* as needed. Then we use three more patterns replacing G1 and G3 with G2 and G4 respectively to force 0x (with GE6 a "copy" of GE3).
GE1 through GE6 presented in Fig. 16 will be used to force the last glue names of the RAB and UAB tile types. And symmetrically once again, GE7 through GE12 in Fig. 17 will serve the same purpose for RAW and UAW. It should be understood that GE4 is then a copy of GE1, except that it has G1 replaced by G2, and G3 replaced by G4. Similarly, GE5 copies GE2.
Proposition 21 If GE1 through GE12 appear as sub-patterns of PATTERN, along with LB1 through LB118, then in any minimum tile type set solving PATTERN, either • the south glues of RAB1 and RAB3 and the north glues of UAB1 and UAB3 are all the same, and • the south glues of RAB2 and RAB4 and the north glues of UAB2 and UAB4 are all the same, and • the south glues of RAW1 and RAW3 and the north glues of UAW1 and UAW3 are all the same, and • the south glues of RAW2 and RAW4 and the north glues of UAW2 and UAW4 are all the same, as we suggest in T ; or the black box must find a minimum tile type set larger than 46.
Proof By symmetry with all three other cases, we only prove the case for the 0* glues (the first claim). We assume that the black box can find a solution using at most 46 tile types, and we start with the glue scheme as in Fig. 15. Now there must be some north glue for tile type UAB1, by choice call it 0*. We know a tile of type UAB1 must be placed at (5, 2) of GE1 in Fig. 16 because the south and west glues match. Then we also know that 0* can't be the same as any of the previously existing vertical glues. If it was, Figure 17: GE7 through GE12 are the analogues to Fig. 16 for RAW and UAW.
then we wouldn't be able to place a tile colored RAB at (5, 3), as its (south,west = 0h) glue pair would require that a tile of a previously described color attach at this index.
In fact, we know exactly what tile type is placed at (5, 3)-it is RAB1 because of its east glue. So we see that the south glue of RAB1 is also 0*. If we look at sub-pattern GE2, we see that a tile of type UAB1 is again placed at (5, 2), this time with type RAB3 above it, so the south glue of RAB3 is 0*. Finally we consider sub-pattern GE3. This time it is type UAB3 that must be placed at (5,2), and match its north glue to the 0* south glue of RAB1.

Proposition 22
If GE1 through GE12 appear as sub-patterns of PATTERN, along with LB1 through LB118, then in any minimum tile type set solving PATTERN, the glues of all tile types that can be used in CIRCUIT must be the same as we suggest in T , up to isomorphic symmetry; or the black box must find a minimum tile type set larger than 46.
Proof Aggregating the results in this Section 5 correctly forces all glue names to match those assigned in T , up to isomorphic symmetry. •

Integration and Correctness
In this Section we prove that 29-PATS is NP-hard. We start by mentioning and dismissing a minor concern with the design-the possibility that the black box could choose a set of elements to subtract such that at some point, the running total "becomes negative" after subtracting some element; then it could keep subtracting elements and eventually reach 0, though this subset does not actually sum to the original target n.
Our design precludes this possibility by requiring the height of the pattern, equal to max( log 2 (n+ Σ all ) , 21), to be sufficiently large: if the running total ever "goes negative," then even by subtracting every remaining element of S, we cannot possibly make it back down to 0 again. When an element is subtracted from the running total, the operation that we are actually performing is subtraction-mod-2 row# , and we use this idea to join together sub-patterns. We can verify that every color sub-pattern begins and ends with a column of squares colored by Black and White, or their copies. Then every east glue and every west glue of every sub-pattern is either 0h or 1h. Taking the italicized text as an invariant gives us the needed result.
Proposition 23 Given 2 sub-patterns P 1 and P 2 of the same height row# such that all of the east glues of P 1 and all of the west glues of P 2 are 0h or 1h, we can join them together into one sub-pattern P * using the tiles of T .
Proof As just explained, our sub-pattern that represents the subtraction of one element from a number "written" vertically is actually subtraction-mod-2 row# . Then we are free to think of both the east glues of P 1 and the west glues of P 2 as respectively input and output numbers mod 2 row# , and we can design the needed subtraction-mod-2 row# to take place in between them. • We have a full description of PATTERN. It lists CIRCUIT, LB1 through LB118, and GE1 through GE12 in order and then joining successively listed sub-patterns together as described in Proposition 23. Theorem 24 combines the goals given at the beginning of Section 3.
Theorem 24 For any instance of Subset Sum SS, if we reduce it to the 29-color pattern PATTERN and submit it to our black box as input, the size of a minimum tile type set that we receive as output will be equal to 46 if and only if SS is satisfiable.
Proof From Proposition 14 we know that the minimum tile set must have size at least 46; and from Proposition 22 we know that if a minimum tile set has size 46, then it must be isomorphic to T , i.e., T describes the necessary tile set if the minimum tile set has size 46.
From Proposition 3, we know that T is sufficient for any solvable SS. Necessity and sufficiency of T for solvable SS completes the "if" direction of our result. Now we show that T is not sufficient if SS is not solvable.
We start by analyzing the extent of the ability of the black box to actually make decisions about glue choice for the sub-pattern CIRCUIT, if it intends to use only 46 tiles. From our discussion in Section 3, we know that it is only for the southern glues of RAB and RAW tiles in the first row that the black box actually gets to make a choice. For RAB tiles it can choose 0* or 0x; for RAW it can choose 1* or 1x. Again by Proposition 3 these choices exactly correspond to subtracting an element of S or not.
However, by the assumption that we are working with an instance SS that is unsolvable, there is no sequence of seed glue choices for RAB and RAW tiles such that the east glues of the secondto-last column in CIRCUIT are all 0h, to match the uniformly 0h west glues required by the last column's uniformly Black squares.
Then because T is forced when we are restricted to at most 46 tile types, it must be the case that for inputs PATTERN that result from reducing unsolvable instances of SS, the black box finds a minimum tile set of size strictly larger than 46. • Theorem 24 directly implies Theorem 1 (our main result which was stated in the Introduction). An instance of Subset Sum SS is solvable if and only if the black box outputs a minimum RTAS size of 46 for an input of PATTERN, completing the reduction.

Corollary 25
The original PATS problem cannot be approximated to within a 47/46 ratio.
Corollary 26 k-PATS is not in PTAS for any k ≥ 29.