{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Week 12: Proving NP-Completeness" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from tock import *\n", "settings.display_direction_as = \"alpha\"\n", "from cooklevin import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Tuesday\n", "\n", "Last time, we showed that the language $\\mathit{TIME}_{\\mathsf{NTM}}$ was NP-complete:\n", "\n", "$$ \\mathit{TIME}_{\\mathsf{NTM}} = \\{ \\langle N, w, \\texttt{1}^t\\rangle \\mid \\text{NTM $N$ accepts $w$ within $t$ steps} \\}. $$\n", "\n", "Today, we start to consider other NP-complete languages." ] }, { "attachments": { "image.png": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXYAAACwCAYAAAAbmEV4AAAMTGlDQ1BJQ0MgUHJvZmlsZQAASImVVwdYU8kWnltSSWiBUKSE3kQRBAJICaFFEJAqiEpIAgklxoSgYkeWVXDtIgrqiq6KuOjqCshasZdFsffFgoqyLq5iQ+VNCujqK9873zd3/pw585+SuXNnANCr4ctk+ag+AAXSQnlCZChrXFo6i/QQoMACmAAnwOILFDJOfHwMgDLQ/1NeXwWIqr/kruL6dvy/ioFQpBAAgMRDnCVUCAog/hUAvEQgkxcCQGRDvd3UQpkKZ0BsJIcBQixT4RwNLlXhLA2uUtskJXAh3gEAmcbny3MA0G2GelaRIAfy6F6H2EMqlEgB0CNDHCQQ84UQR0E8tKBgsgpDO+Cc9QVPzj84swY5+fycQazJRS3kMIlCls+f/n+W439LQb5ywIcjbDSxPCpBlTOs2/W8ydEqTIO4W5oVGwexIcRvJUK1PcQoVayMStbYoxYCBRfWDDAh9hDyw6IhtoA4QpofG6PVZ2VLIngQwxWCTpMU8pK0cxeIFOGJWs4a+eSEuAGcLedytHMb+HK1X5X9MWVeMkfLf10s4g3wvyoWJ6VCTAUAoxZJUmIh1oXYSJGXGK2xwWyLxdzYARu5MkEVvz3EbJE0MlTDj2VkyyMStPayAsVAvliZWMKL1eKqQnFSlKY+2HYBXx2/KcSNIikneYBHpBgXM5CLUBQWrskdaxNJk7X5YndlhaEJ2rk9svx4rT1OFuVHqvS2EJsrihK1c/FRhXBBavjxGFlhfJImTjwzlz86XhMPXgRiABeEARZQwpYFJoNcIGnrbuqGvzQjEYAP5CAHiIC7VjMwI1U9IoXPRFAM/oRIBBSD80LVoyJQBPUfB7WapzvIVo8WqWfkgUcQF4BokA9/K9WzpIPeUsBDqJF8410AY82HTTX2rY4DNTFajXKAl6U3YEkMJ4YRo4gRRBfcHA/CA/AY+AyBzRNn434D0X62JzwitBPuE64QOgg3JklK5F/FMgZ0QP4IbcZZX2aMO0JObzwUD4TskBln4ubAHR8J/XDwYOjZG2q52rhVubP+TZ6DGXxRc60dxYOCUkwoIRTnr2fquup6D7KoKvplfTSxZg1WlTs48rV/7hd1FsI++mtLbAG2BzuJHcFOY/uxJsDCDmHN2DnsgAoPrqGH6jU04C1BHU8e5JF844+v9amqpMKj3qPL44N2DBSKpqn2R8CdLJsul+SIC1kcuPOLWDypYNhQlqeHpwcAqu+IZpt6yVR/HxDmmc+6+TYABE7v7+/f/1kXfQGAPQfga37zs86pE24HZwA4tVqglBdpdLjqQYC7gR58o8yAFbADzjAjT+ADAkAICAejQRxIAmlgIqyzGK5nOZgKZoJ5oAxUgKVgFVgLNoBNYBv4GewGTWA/OAJOgLPgArgCbsH10wmegR7wGvQhCEJC6AgDMUOsEQfEDfFE2EgQEo7EIAlIGpKJ5CBSRInMROYjFchyZC2yEalDfkH2IUeQ00g7cgO5h3QhfyPvUQyloUaoJeqIDkfZKAeNRpPQCWgOOgUtRkvRxWgVWovuQBvRI+hZ9AragT5DezGA6WBMzAZzx9gYF4vD0rFsTI7NxsqxSqwWa8Ba4D99CevAurF3OBFn4CzcHa7hKDwZF+BT8Nn4Inwtvg1vxI/hl/B7eA/+iUAnWBDcCP4EHmEcIYcwlVBGqCRsIewlHIdvUyfhNZFIZBKdiL7wbUwj5hJnEBcR1xF3Eg8T24kPiL0kEsmM5EYKJMWR+KRCUhlpDWkH6RDpIqmT9JasQ7Yme5IjyOlkKbmEXEneTj5Ivkh+TO6j6FMcKP6UOIqQMp2yhLKZ0kI5T+mk9FENqE7UQGoSNZc6j1pFbaAep96mvtTR0bHV8dMZqyPRmatTpbNL55TOPZ13NEOaK41Ly6ApaYtpW2mHaTdoL+l0uiM9hJ5OL6QvptfRj9Lv0t/qMnSH6fJ0hbpzdKt1G3Uv6j7Xo+g56HH0JuoV61Xq7dE7r9etT9F31Ofq8/Vn61fr79O/pt9rwDAYYRBnUGCwyGC7wWmDJ4YkQ0fDcEOhYanhJsOjhg8YGMOOwWUIGPMZmxnHGZ1GRCMnI55RrlGF0c9GbUY9xobGI41TjKcZVxsfMO5gYkxHJo+Zz1zC3M28ynxvYmnCMRGZLDRpMLlo8sZ0iGmIqci03HSn6RXT92Yss3CzPLNlZk1md8xxc1fzseZTzdebHzfvHmI0JGCIYEj5kN1DblqgFq4WCRYzLDZZnLPotbSyjLSUWa6xPGrZbcW0CrHKtVppddCqy5phHWQtsV5pfcj6KcuYxWHls6pYx1g9NhY2UTZKm402bTZ9tk62ybYltjtt79hR7dh22XYr7Vrteuyt7cfYz7Svt7/pQHFgO4gdVjucdHjj6OSY6vi9Y5PjEydTJ55TsVO9021nunOw8xTnWufLLkQXtkueyzqXC66oq7er2LXa9bwb6ubjJnFb59Y+lDDUb6h0aO3Qa+40d457kXu9+71hzGExw0qGNQ17Ptx+ePrwZcNPDv/k4e2R77HZ49YIwxGjR5SMaBnxt6erp8Cz2vOyF90rwmuOV7PXi5FuI0Uj14+87s3wHuP9vXer90cfXx+5T4NPl6+9b6Zvje81thE7nr2IfcqP4BfqN8dvv987fx//Qv/d/n8FuAfkBWwPeDLKaZRo1OZRDwJtA/mBGwM7glhBmUE/BnUE2wTzg2uD74fYhQhDtoQ85rhwcjk7OM9DPULloXtD33D9ubO4h8OwsMiw8rC2cMPw5PC14XcjbCNyIuojeiK9I2dEHo4iREVHLYu6xrPkCXh1vJ7RvqNnjT4WTYtOjF4bfT/GNUYe0zIGHTN6zIoxt2MdYqWxTXEgjhe3Iu5OvFP8lPjfxhLHxo+tHvsoYUTCzISTiYzESYnbE18nhSYtSbqV7JysTG5N0UvJSKlLeZMalro8tWPc8HGzxp1NM0+TpDWnk9JT0rek944PH79qfGeGd0ZZxtUJThOmTTg90Xxi/sQDk/Qm8SftySRkpmZuz/zAj+PX8nuzeFk1WT0CrmC14JkwRLhS2CUKFC0XPc4OzF6e/SQnMGdFTpc4WFwp7pZwJWslL3KjcjfkvsmLy9ua15+fmr+zgFyQWbBPaijNkx6bbDV52uR2mZusTNYxxX/Kqik98mj5FgWimKBoLjSCB/ZzSmfld8p7RUFF1UVvp6ZM3TPNYJp02rnprtMXTn9cHFH80wx8hmBG60ybmfNm3pvFmbVxNjI7a3brHLs5pXM650bO3TaPOi9v3u8lHiXLS17NT53fUmpZOrf0wXeR39WX6ZbJy659H/D9hgX4AsmCtoVeC9cs/FQuLD9T4VFRWfFhkWDRmR9G/FD1Q//i7MVtS3yWrF9KXCpdenVZ8LJtyw2WFy9/sGLMisaVrJXlK1+tmrTqdOXIyg2rqauVqzuqYqqa19ivWbrmw1rx2ivVodU7ayxqFta8WSdcd3F9yPqGDZYbKja8/1Hy4/WNkRsbax1rKzcRNxVterQ5ZfPJn9g/1W0x31Kx5eNW6daObQnbjtX51tVtt9i+pB6tV9Z37cjYceHnsJ+bG9wbNu5k7qzYBXYpdz39JfOXq7ujd7fuYe9p+NXh15q9jL3ljUjj9MaeJnFTR3Nac/u+0ftaWwJa9v427Let+232Vx8wPrDkIPVg6cH+Q8WHeg/LDncfyTnyoHVS662j445ePjb2WNvx6OOnTkScOHqSc/LQqcBT+0/7n953hn2m6azP2cZz3uf2/u79+942n7bG877nmy/4XWhpH9V+8GLwxSOXwi6duMy7fPZK7JX2q8lXr1/LuNZxXXj9yY38Gy9uFt3suzX3NuF2+R39O5V3Le7W/uHyx84On44D98LunbufeP/WA8GDZw8VDz90lj6iP6p8bP247onnk/1dEV0Xno5/2vlM9qyvu+xPgz9rnjs///WvkL/O9Yzr6Xwhf9H/96KXZi+3vhr5qrU3vvfu64LXfW/K35q93faO/e7k+9T3j/umfiB9qPro8rHlU/Sn2/0F/f0yvpyvPgpgsKHZ2QD8vRUAehoADHiGoI7X3PPUgmjupmoE/hPW3AXV4gNAA+xUx3XuYQB2weY4F3LDXnVUTwoBqJfXYNOKItvLU8NFgzcewtv+/peWAJBaAPgo7+/vW9ff/3EzDPYGAIenaO6XKiHCu8GPYSp0Y0WcDHwl/wLnqIEjuo16QwAAADhlWElmTU0AKgAAAAgAAYdpAAQAAAABAAAAGgAAAAAAAqACAAQAAAABAAABdqADAAQAAAABAAAAsAAAAABcOZq5AAAzrklEQVR4Ae2dCfxUY/v/b2uyJcnWYyuFIoVUiFAJWR5L9iXZkzVkC3mSfXmKsmXNLmRJaBUpolRCiyVCtpIt/Jz//b7/r3ueM+c7851zZubMnOW6Xq95zcyZ+9zL55y5znVf6wqOJiUkCAgCgoAgkBgEVkzMSmQhgoAgIAgIAgYBYexyIwgCgoAgkDAEhLEn7ILKcgQBQUAQEMYu94AgIAgIAglDQBh7wi6oLEcQEAQEgZUFAn8I/PDDD2r27Nnqo48+UgsWLFCLFi1SX3/9tVqyZIn69ddf1R9//GE6WmmllVTdunXVOuuso+rXr6823nhjtemmm6ottthCbbvttmqrrbZSq6yyir9BpZUgIAgIAkUgsIK4O+ZGbfHixerll19WY8aMUW+//bb6/vvvVfPmzdXWW29tmPMGG2ygGjVqpOrVq6fWWGMN8/q///s/xWv58uXqxx9/VD///LP64osvzOvzzz9X06dPVwsXLlTbbLON2nXXXdXuu++uOnfurNZaa63ck5CjgoAgIAgUgYAwdhdoMO8nn3xSPfzww2rOnDmqS5cuat9991U777yzatGihatl8R///PNP9c4776g333xTTZw4UU2YMEG1bdtWHXnkkerwww83D4rie5czBQFBQBBQShi7vgtg4rfccosaMWKE2meffVSPHj3UnnvuqVZeOXxN1W+//WZ2BQ8++KB5P/DAA9UFF1ygWrZsKfenICAICAJFIZBq4+mXX36pTjzxRLX33nurTTbZRM2fP189+uijRj1SCabOFVt99dXVAQccoJ5++mn12WefGXUPu4T9999fffDBB0VdVDlJEBAE0o1AKhn7P//8owYNGqRat25tjJsw9H79+hmDZzVvB/T1F198sWHwMHZUQaeddpox0FZzXjK2ICAIxAuB1Kli0KMfccQRxpPliSeeUJtttllkr9iyZctU37591ciRI43ev2PHjpGdq0xMEBAEooNAqiR2VB0YKvfYYw9jvIwyU+cWwVvmjjvuUI888oh5GN14443RuXNkJoKAIBBZBFIjsSOpN2zYUA0ePFj16tUrshck38Rwl+zWrZs6+eST1TnnnJOvmRwXBAQBQSAdXjEYSXfZZRdjkBwyZEhsL/t3332n1l9/fXX33XerU045JbbrkIkLAoJAuAgkXmL/+++/FbrpQw45RJ1//vnholmB3jH08pB66qmnTIBTsUPykMDr5pNPPjHBVwRU8VpxxRVNsBXeOhtttJFq1qyZeTVu3FgRVSskCAgC0Ucg8Yz9mmuuMfr0V155JfpXw+cMX3/9dXX66aerWbNmqdVWW83XWb///ruJpAUHommXLl2qtttuOxN4te666ypeqKr++usvY1jGv56UCaRQgPnzICBadq+99jLuoK1atfI1rjQSBASByiOQaMZOPhfys8ycOdOE/1ce3vBGxLNnhx12MO6RtY0yefJkddddd6nnnnvOSPpdu3Y1QVjkrAlCPAjGjh1rXqNHj1Z16tRRxx13nDrmmGMSh20QXKStIBBFBBLN2PEBX2+99dSAAQOiiH1Jc3r//ffVwQcfbHzeV1hhhRp9jRo1yqwbSRt9/AknnGAk8hoNizzwxhtvGBfMZ555RhEti1tm0IdFkUPLaYKAIFAIAZKAJZF0Ai5n7bXXdrQ3TBKXZ9bUvn1757XXXstan2b4jk6H4OidivP4449n/RbGF3DW6i5HP0Cdww47zNEupWEMI30KAoJAAAQS68eumZrRBTdo0KDQsy22v3fo0EGhaoHQoZ977rlGzXLssceqGTNmGN/3sBeHr/3ll19uMljutNNORj105ZVXKnT0QoKAIFAdBMLPclXkuvDbJjnXvHnz1DfffKPIh046XP3QUquuuqrJgojr37/+9S/VtGlTkwoXTw5LL730ktH/2u9JfMc7ZtiwYerdd99VRx99tDFufvjhh6oaDzNy0JMOAZ37hRdeqDCuElhFZkwhQUAQqCwCkdGxw7jJrojXxqRJkwzzJvc5Lxg4+c9JzMUL6fSXX34xxS6++uor9fHHH6u5c+eaghZElpKZ8eyzz1YwOQpdJJXGjx9v1go+RKhqVUhkloqxFhsHLyR4cZWMzKWRiaQAgaoydpJxaR2xuu+++xSeFmQ5JLMhBSjIthiEKHCB+9/UqVNNpkRUBGRMTDLhd77jjjsaTxUqNEWNcJckBTLXmTz3VJUSEgQEgfARqBpjRzq/4oorTNranj17GlWCNnaGv+KEjUDhDlRTUabzzjtPoRpDiqcKlZAgIAiEi0DFGftbb71ljHxEhF533XUmNW24S5Teo4AAtoBLL73UBEnhfy8kCAgC4SFQMcZOseerrrrK+D5Trah79+4ql/91eEuVnquNAOo2PHYoC0iqAiFBQBAIB4GKuDsSlt6mTRsTmk5+EqImhamHc0Gj3CtlBy+77DITyIQ9REgQEATCQSB0xo7nBvnPL7roIuP1Ug1XvHCgk16LQQBfexKYderUyTzoi+lDzhEEBIHaEQjVjx0D6RlnnKGoVESGRSFBAARwy8RdFQmeAKsNN9xQgBEEBIEyIhCajv3FF1807otEQLZs2bKMU5aukoIAxvMXXnhBsatbZZVVkrIsWYcgUHUEQlHFkBiKSj9IY8LUq36NIzsBIlXr169fMENlZBcgExMEIopA2Rn7q6++qs466yw1YcIE1a5du4guW6YVBQQwoA8fPtwU60ZtJ5QbAWIVEJYI4AMvIUGgEAJlZeyUoCNH96OPPiopXAshL78bBOrVq2eY1ZlnnmnyAQks/0PgnXfeMUISlaywS6DexG1YSBAohEDZdOwk6Nptt92MK2OfPn0KjSu/CwJZCJA4DMHgscceyzqeti+kYXj44YfVgw8+aHId2fVT7er44483KRrEs8yiIu/5ECgbY+/du7epkUl0oZAgEBQB1A3bb7+9uv76603hjqDnx7k9Uvjzzz+vHnjgAZM7ibxHEInvyNoJQ5dShHG+wpWfe1kYO0ZSikXPnj3b1M6s/DJkxCQgQNUn8soQvEQWzzQQ7sDUDliyZIlZLjVsqYwFM+/SpYtkxUzDTRDCGktm7Khg8HwZOHCgYe4hzFG6TBECMLODDjpI9erVq6RVkwuekn1RTyzHA8xK6ERkDxkyxHgKlbR4OTn1CJRsPIWhkzoWiV1IECgVgUGDBqn+/fubAKZS+iK6ldTPPCRg8rqEXyndhXbu/vvvn9mdEMhH8XVsVNOnTw9tTOk4+QiUJLEvXrzYVC6igk8U84En//Ilc4V4gJCTn2IppRDMfOTIkSaFAUFQRD8ffvjhkZPk+R/hxojBlIA+SzB5kqahZw9an8D2Ie/pRKAkxo6LGjpBsjUKCQLlQgBBgR3gggULMtJsqX27mfy4ceMMkyfDaNTUNTB2GDwuw99++61ZNv7+5FuCyTNnisgQsYvB1U0rrriieQBQrIb6s0IpRiBA4euspvPnz3caNmzoUKVeSBAoNwI6SZijpdhyd2v6457V6hlHM3VHM0lHB/44Dz30kLN06dJQxium07/++svRzNvRuxenTp06jmZR5nXvvfea7nSRGvNd+7g7W265pXlpIcsc0wzeGTp0aDHDyjkJQaBoHfttt92mqHyE9CAkCJQbAe4tJNcwiHuWottIvNTMxWhJZCeF0ZHg8SNHwq8mYVTt1q2bUSPh237nnXcq6vm6C7YzPypTUe+XF6USUT0huRMXYI2y1VyHjF0dBIpSxXADNWnSRM2ZM0cy81XnuiV+VHy7KUQ+c+ZM1ahRo4qsd9myZRmd/NixY426xurkiZANg1C5aCHRd9ek6eC/169fP3XNNdeo9957T7Vu3TrrfB4IMPx58+aZtlk/ypdUIFCUszDSA1KOpFtNxT1SlUViu8FoiEcLycIqQVaSR5p3M3lcL9FxW518OZk8/upBJGutiinIrL/55hsDl1e6rwSGMkY0EAjM2JEu7r//flN1PhpLkFkkFQEkz2uvvbZijN2No5vJkzseFceTTz5p/Oth8kjyuFKWyuQJyPrnn3/cQ9f6GXWMmxYuXJjx1f/000/NPKdNm6aaNm1qIsHdbeVzehAIrIqZOHGiubnZIgsJAmEigDpGG+hNDplSGWi55mmZPH7yY8aMMZJ8uZh8kDlaVUyuc7AV8BBq3759rp/lWAoQCCyxI6336NEjBdDIEquNAOqYjtr3/PXXX1eHHnpotadjxl9zzTWNigg1kZvJk6q6nJK838XecMMNqnHjxqY5bpHYI4gEr1u3rt8upF0CEQgksWsXLJOYiOLU66+/fgLhkCVFDQFUMeRRgYFFmdxMHkmeACt08uVQ1+Rat5XYcxlPc7WXY+lCIJC7I2qYZs2aCVNP1z1S1dXusMMOxvOjqpPwMbiV5J999lm1aNEi407JZyJGsRXguqn95H30JE0EgdIRCMTYMSDh5yskCFQKgbgwdjceMPmjjjpKuZk8PvPC5N0oyecwEQjE2PGN/fe//x3mfKRvQSALAVR+K620UmyrK1kmT+k/K8l7mbxN2Zu1cJ9fCEYSEgS8CPjWsXNTUsXlhx9+8PYh3wWBUBHAGEg0KIU4kkLo5Mn3gncNxuEOHTpkdPLrrLNOUpYp66gSAr4f92+88Ya5+ao0Txk2xQgQgYpgkSRyS/KkDKBWMJL8pptuqkjlSzWlUiT5JGElawmOgG/GPmnSJFPTNPgQcoYgUBoCRDh/9913pXUS4bPXWGMNdeSRRyrUNZbJI80Lk4/wRYv41HwzdlKp7rrrrhFfjkwvqQgEic6MMwaWyZOULB+T/+mnn+K8RJl7BRDwxdhJI0CkaYsWLSowJRlCEMhGAONpkHwq2WfH91s+Jr/55pur/fbbz6hrhMnH9/qGOXNfjP3zzz83dRijXj8yTKCk7+ohAGMPkgGxejMNb2Q3k8fecMIJJxjjq2XyRIQLkw8P/7j17Iuxz549O1EeCXG7SGmfLyoJiXT+310Ak7c55C2TxxVZmPz/MEr7J1+M/bPPPjOGnLSDJeuvDgLUBBXGnht7y+Sffvpp4zmEJC9MPjdWaTrqi7F/+eWXprpMmoCRtUYHATxihLEXvh75mPxmm22mqIMq6prCGCalhTD2pFzJhK4DX24Y+xZbbJHQFYazLDeTp/AGGVmR5C2THzZsmOjkw4E+Er36YuzoOMnxLCQIVBoBm72QlLRCxSFAJSUyTaKusUx+1KhRwuSLgzMWZ/li7IQ/S5mtWFzPxE1y+vTpqlWrVolbV7UWZJk8qQzyMXlqGheijz/+uFAT+b2KCPhm7IRACwkClUbgxRdfVJ06dar0sKkYLx+TR+3VtWtXhbomF5MfNGiQ2nrrrU2em1QAFcNF+koCxoWeMGGCeMbE8ALHecr4ZRNWj46dakpClUHgt99+M/p4yuu9+uqrpsQe5f/I7LruuusatexXX31lqjRROeq6665TkmWyMtfG7yi+JPY0Rv35BVDahYcAxj6kdWHq4WGcq2ckeRg56hrsaz179lSjR482BmzSithAqN9//13dcccd5hr9/PPPubqSY1VCwBdjX3nlldXff/9dpSnKsGlF4M4771THH398apb/559/KnLEHHDAAWr48OGRWLdl8kjvNlCMEpmWkO7feust1bx5c/XJJ5/Yw/JeZQSEsVf5AsjwuRGYOnWqYSTUDE06vfPOOwqVxkYbbaQOO+wwhV3hjz/+iNyyYfLM1c3YmeTy5ctNcBTVrqZMmRK5eadxQiv7WfQqq6yi0pJdzw8e0iZ8BG677TZ17rnnJlZ3i/RL8RBqoX744YcZQClmwy7l4IMPzhyLygc8YdCtr7XWWgr3U+uCSh4fXjD4du3apT6vTxSuly/Gvt5666lvv/3WWMKjMGmZQ7IRQFofP368uvvuuxO1UKRwimlQROO1117LZKzcYIMN1NFHH20YepRdO7faaiuzm1i2bJlxf65bt26Nd7HHReOW9cXYGzZsmOhCB9G4FDILEEDy69Wrl7rhhhtUklxszzjjDPX4449nqiJhEMZAiXTepUsXU9c1DncA1Z2Eoo+AL8ZOno7vv/8++quRGcYegYceekhhrD/mmGNivxb3Au65556MhE5mxiFDhphU2O428rm8CMydO1e9+eab6tNPP1ULFiwwwinVuHDf3lzntG/Tpo0x+pYyKrsXt6//qquuamwl3j5xPkGNVU5CRU7ZyFzki7GTX2LevHm5zk/kMe/FIu8G6qgghIcDelRL9evXV9589kT0BikOjvGK3VNSiT9gnz591NixYzP626SsFUn35ZdfNt5lTzzxhKKG8FFHHaWOPfbY1EfWknqYdAczZsxQH3zwgWHCqKeaNGmittxyS3XSSScpbA9+CS8ddnwjR46sVd+PjQDj/JVXXln0NTj55JMVHkOWUE/xv69Xr549ZN6pacFayknbbLNNln0mq2+99S1Izz77rNOtW7eC7ZLSQBvuHA1S5qWDMhwdfh1oeTrHSeZ8+rr++utrnH/XXXdltXGPme+zfjg4O+64o6O38M6cOXNq9BnXA/pB6Oy8887OrbfeGtclFJy3tlM5t9xyi7P99ttnXfdtt93W0UE+zhdffFGwj6Q10EzR4f+V737nuGbAjlZbOTp9eMHln3feebX2lW+cfv36Fezb20AHzjlaQq8xnvbt9zZ15s+fX6Ndvrn4Pa4Ze41x7AGeaAVJW+2dpk2bFmyXlAZexg7Q2g0t0PLCYuzui663Yk7fvn0dHSgSaG5RbMyDSktOUZxaKHPSOXAcmJCWTDN/eBhYx44dnXvvvdfRAT9mXC11OjpAKOt1yimnOP3793e062Eoc6tUp5dccklm7e77Ot9nLbU7v/76a97pITx5zwVTrXIxDwbusT333NPRbqU12nGe3jXk7TvXDwgh3vH43rp16xrNI8nYkaa0IatWUGusJMYHcjF2LpgOHvG9qkowdntTabdA3/OKYsOLL77Y0W5yiXhABcVX+4Q7L7zwghEc6tSpk2EUMHfoiiuuMMdgRnorb17a8GqO6TB+Z+jQoUGHjER7XUPZ0SUPM+vlXtZRxs7tt9/uvP76686jjz7qaFuEkdbtfc67LiSSc/5afVejrVaTOFq3XqO99txxtCHb0flussaHx2mXzhrt8x1gp+Wem/vztGnTsk7TrqCOVjPV+jr00EOz+tNeYQ445XvpgLCsMdxffEnsnNChQwdHu2i5z03s53yMnT+XNpT4WncxjP2iiy7KeeG17tHROTuMJHfiiSc62riYdQPwB/HeSL4mGYFGWn9qVBPa1hCB2VR3CtxbOtrWadu2rWFszMYydu4nSzra00GS5z7QPuWONszZn2LzDhN3M8L//Oc/jo6VqTF/ncog6wHAvc76vaRtM1n9ac8qb5Ma31GlaENq1nnMww+9/fbbWeddcMEFWd+1F5SfbrLanH322Vl9lMJvfRlP9QVQ5IjAwpzmTHsYRfQFNFnvwKTchIW7kJGIvB16C6s6d+6stE7WTAHf4WuuuUZpW0i5pxRqfx999JFx88MozL2FgTGpyaS0BFqrIc8CjYG9d+/eStsb7KEa7xjoSDuwzz77mGRdlK7E0BgXIiZGS+WZ6eLuedlll2W+uz/wm2Z4Sqs9zGHudQys+uHnbmaM0e4D+oHo/przMw4RGLLdWGuGnbOt96DeUWUO6Z2Wuvzyy9XEiRNNZC4/cL1vvvlmkygt07CSH7IeGbV80QmZnL333ruWFsn5KZ/Erq+LeaIiPRcir8SOccxLXuMp4/qlMWPGZD3d9R/b76mRase2WCebclq2bGmMwuiek0hetYO9l/K9e1Uxbond4oMRnfO1V4k9FIt3JFH3ulGj1EbPPfdcVnt2NW7CxoS9yfapBST3zwU/6yJCmXMbNGhQsL32mjOqaTuetb95+YaOKi7Yl7tBVSR2zdRNdBwpVJPscqcvVg1CSr7vvvsyx0899VQ1a9YshRtktWivvfYy/rLWpRKpjZBupIc4ERI6+VG0ftEE8LAjPO2004wEh2SaFNKG0kBpObwS6cKFCzPusriF4sqn1W9KOzXk9JuOMm5I3G7SDyj31xqfvelMtAG1Rhv3AQqIBKnTjMsprqgQ/2kSm7GLzEe4N+KqbOm4444zH4888kizo2dXASHVE4BWDfKtioFhkHyfkGh8N9NEMHYYp5aSzbL5fOmllypt6KkqDPjFWsbOzYSvbLNmzao6p2IHx6cYv24eWGeeeabSNh3zZ0tKEesbb7yxWGjMebmSoVGuklwzcSOiblEjQUQXe+M7vOuhFoSbvPc4/e20005q8uTJphkPgquuukqRHZSAoUI0cOBAxcsvudUwWsI3hcI5F997BBNSHEPEKpBfh1QMlSZf2R3tpEi0T47mtBFMh8hBt4Q+ePDgzI1ULTy80cBBg6iqNe/axuXPQepapHgSSkme7/+PFgE3BPHwAh90waTJbd++fW1wRvI3HtyvvPKKebGe2ohgNXK+WyJyNJedD0HATeywybtDpkx2suUiErbZBwh9IqUTAWoJ6d9N7p2++3jYnwMx9kMOOcREh+nAmLDnFbn+CUMeMGBAZl5IBUjy5bxpMp37+IBKjJBpSzB1qtskhbR/vjFqEcGHGiLtBDNDXcWL/yGqmiSpqtzXF1ULtW4xIu+7776ZWhCsV7t35lSTnH766apRo0bubhR8CiMzUjU7Hq0DN2mFiQovlryM2qphbH9k5XSrcUiR4U1zbNuG+R6IsfNkAkBqHqaRuNHcEhI3jnaPqgoUXAd38RNqUCaNSJqlg06Mt4xbp5m0dcZpPaQWCStXPF5dMG/SAusgH8Wu2DJhSiROmjTJMOhceCF4Id2T095LPCiwSWDnYBeI6geVH7sgr77fe677O3Mh1bIl7BteWwiqJXfKZTyAdJyCPaVi74EYO7PCcIiLEBJj2ghDH09st4ESxhPk5igFM5785MHgphwxYkRWV+ink0jat1/paExTV1N7ECRxibFaE8wM5oskzD1IebxyEQyYh0au68zODX2115DqHhvdO/lmdHqAWnM7scseN26c0oFxSqd3MMzZGk/d/Xk/83Bw8z2vtG7bexPYuXXytk3o7253G7+fCQXu0aOH3+axa+d1W9I6taw1aJ/xjHuUvkCONtzUCBIpxt1RbyUdrRfM+dpkk02yAjUY177IsYLbYFKJyGfyYmhGktQl5l2XDVCKihuoZrCZ+47gKC3kOPvtt59xWdWMOe86/Pyg9e6ZoCt7b3vftU7bIVq3EBHERB4aLYg6uAJ7+8n1fY899nD0zjBv19rgm9VPrqhWTmZ+2nMw05YIYT95gMrp7ug78tS92iVLljjaiGFCXd3Hk/K5EGOH0XgTOXmTfBXD2HPdbIWO6cybJlo1KdjnW4f2jHDwN67tj5fvXDkeDAEtFRucFy9ebBJvkSvq3XffdXQATt6EXTB5GFiLFi2CDZanNbly9O7UOfDAAzMM0v4XiNAOStpOYx4+559/vhGcbF/ed+35l/PBoT3OzPpse4Q5Hh75Xtr+ljXvq6++uuCUy8nYfbs76gVliG0R+ikswvqCp66KPLYGVDLo66yeG/cqvIbYqlaCmIO+Sc22022sqcTY1Rhj9913Ny5yN910k0mzWo05RGFMVB/4WfNyf7bHgrznOx91CPdUrlc+VYjmWkZF6Y7iLAUv9OzYs3CvxiuGmrCWcGMk+nqdddaxhwq+4xqKpxUviFgAPHKuvfbaTPETjuOtg+ujN3L1/vvvz1IDwfeC/O+GDRtmolNR51aCimLsTAz9ko5GNXqqavtzVwIo7xgEVZBeAB07xJ9EZ90zujvcI4sh+nQbXrx94JPbuHFj46tudZ3eNkn+jvEL7xD+1H78kyuJBYa1IEy1WMaMz7ZluOi67efa3vGYyvV7vvM5no/IAa537OZnmBTzwbBJXEf37t2z7E/5+gh6nIpalBKEyUMY0nX0txkvaF+2PcbWCy+8UFH0hLKEpLSwRLoDN2PnYQZjLoWIMaFfUiRUgopm7EwOqzVWYRhStSKsKgFSvjGQ0rHk408MEUih0wQYz6F859R2nIflOeecU1uTVP+mt/kmlw7eMn7vNwK3MMrlYrr5JNZcbXMdc58Pk8vFPGs7hncGftm1tfH+VqzQUK4bh3Va5wGtJlEYtwkO8kvgaAP9OAdfc20/Kng6ZQQtY6cxFZEssZuzeZNweXQzadsm3zsPJYK83EUwkMbZiVPJC4Ih2/7z9ePnOEbUWDB2JAGepLvttptZl98/mx8Q4tAGaQWVDDcWW1EIS7suShKH6cdyjkhvbM0L3Wts02EiMHYCy7wMku/5JFZ+yyfluvtxn2+ZQCxBDTBpdkswVa4D/uFBiYAzHgiWdF75LOnYHve+s1Nwk9s7hd0SEjHEOy6GBLr5JRKoITTMnj3bnMJ9Q4I6nZbXfPd6tfz3v/817Qv1z84C9axVX/FgIqiQeytsKkliZ3KoBgid5YkHk3f7eYY9+Sj0z0ONSDobHceNi4852RaFyo8Aqhh2NuBcWyg6aR9gwlFT2ZQfkcr26I2sDDo6OxTKRP7000/mVJ1r3FcXulBFVjs3o/cGJiGxE8QVhLxBRFYdBSN27xQYi4eaX105rsk2kyUPIAKWsI2FTWXR5PPEAwCixXTRh6wEOWEvIAr968yNirqwlrA9DB8+3H6V9zIigPRN+DhGrtoIiV2Yem0IVe83pGNL+I/7KfLsDfKhELUlm3fGfkffbx8c9lht79RctepU2sG0rXoIQRWGbIkHm1+mzjleX3dv5Krtt9zvZWHsTIptGfkr2AaR9MZd4LXck45af0SboVt3E7mYhcJBAKk9iB41nFlIr8Ui4M7miP0DCdaqMnP1iZDk1gSwE7NqEtojnbt3bwQyoQJBpVKIKFyP8dRN1AWwQoFXDaMrOLmbFvzM3JivJXLNEGQYNpWNsTNRpKnHHnvMJCnCHZKorgceeKBq+VTCBs/dP1JD0IvuPl8++0eA++r999/3f4K0jBQCSNRu/TxCICoLXBDdpP3ojdpDVw1zHzZ2LJ3fPnMMnTWFLdySNI4M7KLR4XuT5XEiDJ2HBapUd/ZI7Ga26AfJvmDElnDldKuA7PHa3hH6eMi4yfuwcP9Wts8FveaLbECQA5Fk+unsaJ2arwrjRQ5V9tMKBSjlG5DybgRu6YtT41XuQhv55pCG4+BMQIxQfBHQUniN/wj/G/4/u+yyiylZpxl1jTZEucJbchFBgrn+exzT6Z8dIrSJLtXM2dEMvEZbomjhWZa8QUbajmZ/CvROn+55aQE4U6zc3VE5A5TKKrHryWcItyyefrgJEQjg1kFnGiXsA9kVcQEVChcBcMa4hUQnFE8EUH+wq2eX7yaKZKCqQHq33iT2d7zNHnnkEZXP5RPXS5Ly5Qpc4l6ZOnWqkc5J3udNZIZkjeuy1dfj0UJOLEuoZgjILIZQHWI0toT6Cc1GmBQaY58yZYoJIAAstllpIZtaNS3rrdY62X4LY68W+uUZlwAh9OEksPMyeDsCKhf4B8weAyoeNbURahRcHoko9VPprXnz5kYYw4BLimBLeLLA3C3hollsWmzW4NXj63J/tuvMuxcD7/dMQx8fVmAr4KNdoCZcLHy7idbCEBE3QgdGFKklsjcWKjJt2/KO1MEN47bMI8njJuUmjEJu9zGKeaStOpUbjyCf+bPzJ6Zko1D8EYANwVzhHezyqZxFdDURou5CFkFWigsjbq/43fNiF2A9XghMom+3ETZI31FvW3bGTuAA0ahsibxPqaiDIfOLDwJsi9kdEZEoJAgIAtkIlFUVg78nuU7IRyxMPRto+VZeBIgoFRIEBIHcCJSVsZMUi2T3EnWZG2w5Wj4E2LrnM6KVbxTpSRCIJwIlpxSwy6bINdGA06ZNs4fkXRAIDQG3H3Nog0jHgkBMESgLY8foQb4UUmm6I8BiiolMOwYIEHRSyEMiBsuQKQoCoSBQFlXMSSedpPr06WMK0IYyS+lUEPAggJHejzub57TIfKUoNDm/O3bsGJk5yUSSg0DJEjsue/gTw9iFBIFKIYDEXon0p+VcDxkpCZ8nzYbNdUNln7jQjz/+qE477TTjjkgeFoJ87AvHCY6RxzwED+q4QBSZeZbE2JcuXWoYOhnaROcZmWua+Ingn0wVnyA5t6sFCtGTBLtQzIFgPYpzQASfkENEF4Wv1tQCj0uBDaLI8xGR5pQuFKo+AiUxdsrCEa3VunXr6q9EZpAaBObOnWvKsUVZmKBQA8ycRFM2LS3BMQRWUSQEH3zC2ONEPIwI3KP+p631a+dPiocBAwZIBTALSJXfi2bsX3/9tbr77rszVUeqvA4ZPkUIEJ1IaugoEpkCqaJFSg1LZASEmRPfYfN829/i9A7u7Di8bqZI6hSYPtGThTFOa0vaXIs2npJvnHD4OGyHk3bR0r4eiiJElbFTTcwydVQXVN8h9Wvfvn1jydQJBBsxYoQpIk6akM033zwrvQZMnZS5wtQj9q/Uho7ApPWbjk6I4+icKIHPlRMEgVIR0AmZHG2ELLWbUM7XiaocnYckk6ZVq4uczp07O1ot4+gc4KGMGUan/Ld1oKGz8cYbOzpnuaOZt6MNpGaoZ555xtHZDh2tfnF0Ocwwhpc+S0QAC3ZgIl+5zsgW+Dw5QRAoBwLazdFZuHBhOboKpQ/yhY8dO9bRhVccrZfOMHldScfRqTYc7WzgaANwKGOX2qnecTg6D49Tr14959RTT3V0ArwaXbI+nYrWoa1QNBEoKgkYGdHIRNi+ffuI7T9kOklHgAx9VL2xBsmor5fc21rCNYbUcePGZVwByV5IIjNqYu60004KmxV+7V4iVSyl5Eh2hvE1DGKO5DmnIPvy5cszVYsk2DAMtCvUZ9DnjS5Y7Wg9W94qJkH7k/aCQBAEdCro2O4WdZ5wR2c9dXQ62owUr/3YzfKRjPVf3lQb23LLLR1e7Ew4xqtLly5l/89pzx2nd+/eji5M4WjXS0e7ZQa5FNI2wggEFgHwxUXS8FrGK/QckmFSjsBLL72kunbtGksUyAFODnmMvxSOINhH67Cz1sIx3Dl5URie2q5t2rQx6TqIFymVrDGUPPYYQ7XKRc2aNcsYSCW3fanoRuf8wO6O3Fy33HJLdFYgM0kNAjAlbawzrnVRXTRMcsaMGb6m16FDh0wptlwnIDy1atUqoxqh4EuxhWt4SOCePHToUNW4cWPTJ770xRaxyDVfORYdBAIxdkKicd1q165ddFYgM0kNAki5WkVhqutEddGUPMulK883X1IKeKvYe9tSkQvSxlfvTwW/T5o0yZR+I/MqO23eg1QDKziANIgkAoEYO38sDKYrrxzotEguXCYVPwTIS9S9e/dITxyh5/zzz/c9R68qhnws8+fPN+cjSJGO4PbbbzeqT1QnfghjKBGvBA1hDD3rrLOMtC7GUD/oJaNNIK8YqoqzpSM4SUgQqCQChLATDIfOGV110mjmzJmqZcuWOZeFuoTiNUS01kakMcCzBQ8XUheQSlv05rUhltzfAoneqGH23HPP5KIhK4ssAujWiTZNIlN3g45ahtQDlrTHiim4nC/CG7sD6h+k89mzZyvte26MoY0aNbJdyHsKEQjE2LW7VizDolN4XRO3ZBJP6YCfxK3LuyAeXhg1CxF6d2JJMIY2adLESOdiDC2EWnp+D+TuuGjRImHs6bk3IrNS7jt0zW5JNjKTq/BEyEWDEZTEYgRpYQydOHGiOSYeLhW+GBEeLpDEjjEnbqlGI4y9TM0nAkimOoVFau+9X375JRMZSi76Xr16iTHU572T1maBGDsW9mJcrtIKrqy7dAQwmsLYR40aVXpnMevBGkPxBsK2hXcMRlEhQaAQAoEYO7kqqAgjJAhUCgHKyOF3nXTfa9anI9RNAQtyy+DdgrMCxlA8ZsQYWqk7LhnjBGLsa621lvrpp5+kOnwyrn3kV4EQMXDgQJNAK/KTLXGCGEOJDL3rrruMMRR1yyGHHCKRoSXimtbTAxlPN9xwQ2Wj4NIKmKy7cghQX5MAHrI5JpUwhh5xxBHGGEqGx9GjRxtjKMfEGJrUqx7+ugJJ7PjSEqAkJAiEjQC69UsuucTo18Meq9L9Ywy1kaEYQ4kMxY4gkaGVvhLJHS8QYyevRVzyYCf3kqVjZagkdHrbRBkL58yZY3TnlJLDCCrG0HTcy9VYZSBVDAUBJk+eXI15ypgpQgCJtn///ooUFnEndh6olGDkvBo0aGCMofZY3Ncn848mAoFyxRCyTMgz+aSFBIGwECAnyuLFixXRpnEltzGUjJTkbRFjaFyvZvzmHYixI31QqkvXmzQJ+uO3XJlx1BHAtQ/JFrXFeuutF/Xp1pgfUaC4KmIEJagK7xZKSQoJApVEIJAqhnS9ukSXqbZSyUnKWOlAAD9uKghde+21sWLqqI6GDBliGDjzp4AGwo89lo6rJ6uMEgKBGDsTJ9EQARRCgkC5EYARUjWoZ8+e5e46lP7YVeDRsskmm6gxY8aoQYMGmZ0Gx4j5EBIEqoVAIFUMkyRfDKlTv/zyy9Tm7qjWxUryuITP468+ZcoUE6AT1bWijiRNLuoW5kxkaK7apVGdv8wrHQgEZuzAcvTRRys8ZIJUikkHnLLKYhCAWbZt29YwSBhlFAljKC6Y1g0T3TmOBBJEFMWrJXMqirG/++67RiWzYMECtdJKKwmKgkBJCFx00UVGhfHCCy+U1E8YJ2MMHTx4sHr11VeNQANDb9GiRRhDSZ+CQNkQCBSgZEdFWt9ss83MltRPUQB7nrwLAl4EHn/8cWOzmTZtmvenqn3HGPrQQw+ZqkRUKEJnft9994nevGpXRAYOikBREjuD4M7FDY8BSYpbB4Vd2oPArFmzTDpaDI/56n1WEimyKaI7JzK0U6dOxvdcSkFW8grIWOVCILBXjB14n332UQRe8EcQEgSCIkBqiv3339+oOarJ1NHvP/XUU+YBQ+Hnhg0bmtqh9ljQdUl7QSAKCBQtsTN5W9z6448/VhTdFRIE/CDw448/mtD6G2+8UfXp08fPKWVvQyZFmya3WbNmmchQ2X2WHWrpsAoIFC2xM9fmzZubAsMnnXRSFaYuQ8YRgWXLlqkddthBXXfddVVh6hMmTFDdu3c39y6ZSl977TU1fvx4c0yYehzvKJlzLgRKktjp8M8//1Rt2rRR5557rurRo0euMeSYIGAQ+P3331Xnzp0NU0VarhTxMCFNLmpDolvxbDn++OPFGFqpCyDjVByBkhk7M54xY4b5w7799tuqcePGFV+EDBh9BKi8RWQm/uAwWCJMwyavMRSG3rFjx7CHlf4FgaojUJIqxs5+++23VzfddJNh7j/88IM9LO+CgEFg7ty5Zle3dOlS40JYCaYOA7fGUBg8xlBh6nJDpgWBskjsFiwq3lDqa+zYsWrVVVe1h+U9xQig0z7ssMPU9ddfryppi4GRExkqevMU33wpXnpZGTs4Hnzwwer55583uncJt07vnUVgz2WXXaYeeeQRNXz4cLXHHnukFwxZuSBQYQTKztiZ/0EHHWRSDZAFshLb7gpjJsMVQGD69Okm7ws1cu+99161/vrrFzhDfhYEBIFyIlAWHbt3QpT9QmLr16+f+u2337w/y/eEIrBkyRKT7bBr167q5JNPViNHjhSmntBrLcuKNgKhMHZUMDD3zz//XO26664Kf+E4Ex4dQvkRmD9/vjr77LNNJDJ5yAlYO+WUU/KfIL8IAoJAqAiEwtiZMcz9wQcfNOXBSBo2derUUBcSVucwKfKEE3qeZGJnRWK3gQMHmpD6QmslHz/ui6SWaNeunfEJf//999XNN98sZRMLgSe/CwIhI1BUdke/c0K/TkrWrbbaSh1wwAHqnHPOUXjOxEXvTnriAw88UKFiwNsnyQmhSMRFDMKiRYtUt27dFMFERIhSVGWNNdYw3iVkPWQXRtwCgWnkejnjjDMMc69bt67f20LaCQKCQMgIhGI8zTVnkj4de+yxxqhKsYImTZrkahaZY88++6zRFw8bNkyRk5tcOHh5JJWwh7Arod4oBIOHgVO7k8hNIjbXXHNNUwaOVBKbb755bB7QSb1msi5BIC8C+g9bMfrnn38cnfjJWXfddZ3LL7/cWb58ecXG9jvQH3/84ejKUM4WW2zhaO8Oc5ousuBodYPfLmLZTqthMuuN5QJk0oKAIJBBIDQde64nCSoYsvnNnDlTzZs3z+QMoaABHjRRIOwARNF+8cUXisIPfIb22msv9emnnyoiKJNIL7/8sqpfv35mvUlco6xJEEgTAhVl7BbYjTfeWD322GOmKs3999+vSJtKIMtff/1lm1T0HXVDz549Tbm/AQMGmPBzGJ0lyv+hRqpk4io7diXesXv079+/EkPJGIKAIFABBKrC2O26iEYcN26ceuCBB4wHTaNGjVTfvn0VtVQrQVTwoQpUq1atFME05BTJV+oPIzDl0bAVJImuuuoqtdFGGxnjdpLWJWsRBNKMQFUZuwW+Q4cOJi/2W2+9ZdQy7du3VxyjEMMnn3xim5XlnSRllD7bZZddjDdHgwYNjN81RkN8sPMR0ZP4Zl966aX5msTuOJHBQ4cOTexOJHYXRCYsCJQJgYp5xQSZLyoZ3O+IXCTvzNprr22yA7Zt29YwZDxqOFaItCXBuOfNnj1b4bqILvmjjz4yeUuIjMRdDzWLX9KGVdW6dWt19dVXm8IMfs+LYjs8fdgxkWoZXIUEAUEgOQhEkrF74UVlMmXKFPPCwInhlQAoXO5QI5BJcrXVVlOrr766QiLH7/znn382xk505S1atDAMmWAaImFLSU7G+Pjkv/LKK6ZP71zj8H3y5MlmDWThrGa90ThgJXMUBOKIQCwYey5gYeCfffaZ+v77700wDdK0dp80/ub4nMPQYfx+JPtc/dd2bMSIEcaYyi4An+440eDBg42hlJQPu+++e5ymLnMVBAQBnwjElrH7XF9ozUaNGqX2228/RSZD6xYZ2mBl6Jh8Pb179za7mCeeeMJ4IpWhW+lCEBAEIohAJIynEcSl4JT23Xdfo//v1KmTuueeewq2r1YDoknvvPNOo3Jp2rSp0anjXiokCAgCyUVAJPYSry3BVscdd5zJbEh5QNQ/USAYOuoWHeFr0jeQnGvbbbeNwtRkDoKAIBAyAiKxlwjwdtttZ4y6+MKTNAt3SAo2V4u+++47deuttxpmTkAVeXlGjx4tTL1aF0TGFQSqgIAw9jKAXqdOHSMZ472DN84222xjEojhUlgJIkkX5ecOP/xwhbqF5F34qOP1QkFnIUFAEEgXAqKKCeF647FDlCppEshzjpslPvMEXrlTFRQ7NA+P9957T40fP94wbxh5x44dTfFmImdrC7Qqdkw5TxAQBOKDgDD2kK8VOnhUIbwIBiJ1AYVHdPZII10T0Ur0q854qVZccUWF9E8udF6//vqr+vrrr9XixYsVVYpIQkYkLrltdtxxRxOsRYIyCoHgwy8kCAgCggAICGOv4H1AJCyRrx988IEJsiInDm6ISPhLly41SdAwehJwReEKJG8Y/4YbbmiMsqhZKFrCi4eAkCAgCAgCuRAQxp4LFTkmCAgCgkCMERCxL8YXT6YuCAgCgkAuBISx50JFjgkCgoAgEGMEhLHH+OLJ1AUBQUAQyIWAMPZcqMgxQUAQEARijMD/A/S+AStlxjyYAAAAAElFTkSuQmCC" } }, "cell_type": "markdown", "metadata": {}, "source": [ "### Proving NP-completeness using reductions\n", "\n", "
Read Section 7.4, \"The Cook-Levin Theorem.\"
\n", " \n", "q1 | [1] 1 1 1 |
q2 | $ [1] 1 1 |
q3 | $ x [1] 1 |
q4 | $ [x] 1 1 |
q4 | [$] x 1 1 |
q5s | _ [x] 1 1 |
q5s | _ x [1] 1 |
q6 | _ [x] $ 1 |
q6 | [_] x $ 1 |
q7 | _ [x] $ 1 |
q5x | _ _ [$] 1 |
q5x | _ _ $ [1] |
q6 | _ _ [$] x |
q6 | _ [_] $ x |
q7 | _ _ [$] x |
q5s | _ _ _ [x] |
q5s | _ _ _ x [_] |
accept | _ _ _ [x] _ |
Read page 311.
\n", "Watch W12E3: Reducing from 3SAT.
\n", "Watch W12E4: The Clique Problem.
\n", "Re-read the pages on the clique problem, which is scattered across several sections: definition (295-296), membership in NP (296-297), reduction from 3SAT (302-303), and finally NP-completeness (bottom of 311).
\n", "Read pages 312-313.
\n", "Read from the bottom of page 319 to the top of page 322.
\n", "