下载文档原格式
从哈密尔顿图到旅行货郎问题1979年11月7日《纽约时报》出现一篇引人注目的文章，它的标题是：《苏联的发现震动数学界》（Soviet Discovery Rocks World of Mathematics），这文章介绍一个本是默默无闻的年青数学家卡倩（L．G．Khachian），他在线性规划理论上的一个发现使到美国数学界为之轰动。
由于记者在询问一些著名数学家时对数学问题了解不深，文章报导是有一些失实，但由这文章引起的轰动及误导是相当严重。
我以后会讨论这问题。
该文中说：“俄国人的发现建议用电子计算机处理一类和‘旅行货郎问题’（Travelling Salesman Problem）有关的数学上一个著名及难处理的问题。
‘旅行货朗问题’目的是决定一个货郎（或推销员或销货员）所要跑的最短路程──他要走遍市镇，但是不能再回到走过的地方。
表面上，这问题看来简单，事实上为了要解决这问题的实际应用，人们需要电子计算机来解决。
”在这点上这记者是说对了。
“旅行货郎问题”目前是许多国家（如西德、日本、苏联、英国、美国、法国）的运筹学工作者研究的热烈课题。
为了要了解这问题，我们可要知道目前在图论（Graph Theory）上许多人正在研究一种图──哈密尔顿图（Hemiltongraphs）。
一、哈密尔顿图的由来在17—18世纪时，欧洲宫庭及一些贵族很喜欢玩西洋象棋，西洋象棋中的骑士（knight）是对应我们中国象棋的“马”，而它通常是刻成一个马头，跑法也是和中国象棋的“马”一样，走“日”线──即从日的一角沿着对角线跃到另一角。
在1771年，就有一位名叫范德蒙（A．Vandermonde）的法国数学家，写了一篇文章研究所谓“棋盘的骑士问题”。
这问题是这样：在8×8的棋盘格的随意一个位置，我放一个骑士，然后我想法子使他跑遍棋盘的所有的格子，走过的不许再走，我能不能使骑士最后回到原来的位置？这个问题并不简单，许多象棋爱好者及数学家曾坐下来研究这个问题。
离散数学中的图的哈密顿路径问题图论是离散数学中的一个重要研究方向，研究的是图的性质和图之间的关系。
图是由点和边组成的，哈密顿路径问题是图论中比较有名的问题之一，它的研究已经有了一定的发展。
什么是哈密顿路径哈密顿路径是一种在图中遍历每个顶点一次并恰好一次的路径。
换句话说，如果给定的路径经过了所有节点，则称该路径为哈密顿路径。
哈密顿路径问题哈密顿路径问题是指在给定的图中寻找哈密顿路径的问题。
哈密顿路径问题最早由爱尔兰数学家哈密顿提出，他曾经在利用拓扑方法解决多面体问题时，遇到了这个问题。
哈密顿路径问题的正确性还未得到证明，因此在应用中使用时需要适当的限制条件和剪枝技巧。
哈密顿路径的存在性对于一个无向图，若从一个结点开始，遍历每个节点一次，然后回到原来的结点，此时称这样的路径为哈密顿路径。
对于一个有向图，若从一个结点开始，经过每个结点恰好一次，最后回到开始的结点，则称这条路径为哈密顿回路。
哈密顿路径存在性问题是图论中的一个经典问题，它试图回答一个非常基本的问题：“对于任何一个图，该图是否存在哈密顿路径或哈密顿回路？”哈密顿回路的判断对于哈密顿回路的判断，通常使用的方法是基于邻接矩阵和搜索算法。
在搜索算法中，广度优先搜索和深度优先搜索分别应用于无向和有向图。
广度优先搜索：对于一个无向图G和其中的一个顶点v，如果存在一个哈密顿回路，则在G中从v出发的BFS树至少应该包含所有的顶点。
深度优先搜索：对于一个有向图G和其中的一个顶点v，如果存在一个哈密顿回路，则在G中从v出发的DFS树至少应该包含所有的顶点。
如果该树可以拓扑排序，则该图包含哈密顿回路。
哈密顿回路的求解在实际问题中，哈密顿路径/回路问题是非常重要的，其应用很广泛。
哈密顿回路的求解通常使用回溯法，可以按顺序搜索每个顶点，每次选择一个顶点进行搜索时，对于该点已经访问过的顶点进行标记，从未被访问过的顶点中选择一个进行搜索，如果可以找到一个哈密顿回路，则更新答案。
关于路链哈密顿回路的点点滴滴
具有n个节点的赋权网络,有许多话题,除路链哈密顿回路外,还有最小树,最大流等等,无非都是问如何才能最多最快最好最省;
具有n个节点的赋权网络,分为对称与非对称即无向与有向,前者对应一个n阶对称阵a[](a[i,j]==a[j,i]),后者对应一个n阶非对称阵a[](至少有一次
a[i,j]!=a[j,i]);它们的对角线上的元素均为0;
指定起点与终点的最短路,其中间点可有可无,中间点多少不限,该问题有很好的解法;
指定起点与终点的最短链,其中间点当然只能是n-2个,这时,若是非对称的,所有链是(n-2)!条,若是对称的,所有链是(n-2)!/2条;
对于不指定起点与终点的最短链,链中的节点是n个,这时,若是非对称的,所有链是(n)!/2条,若是对称的,所有链是(n)!/2条;
对于哈密顿回路不存在指定起点与终点的问题,这时,若是非对称的,所有回路是(n-1)!条,若是对称的,所有回路是(n-1)!/2条;
最短链与最小哈密顿回路都没找到较好的解法;当n不太大,可由枚举法求解;
最小哈密顿回路的几个简单例子:
最小H回路问题。
哈密顿回路算法概念：哈密顿图：图G的一个回路，若它通过图的每一个节点一次，且仅一次，就是哈密顿回路。
存在哈密顿回路的图就是哈密顿图。
哈密顿图就是从一点出发，经过所有的必须且只能一次，最终回到起点的路径。
图中有的边可以不经过，但是不会有边被经过两次。
与欧拉图的区别：欧拉图讨论的实际上是图上关于边的可行便利问题，而哈密顿图的要求与点有关。
判定：一：Dirac定理（充分条件）设一个无向图中有N个顶点，若所有顶点的度数大于等于N/2，则哈密顿回路一定存在。
（N/2指的是⌈N/2⌉，向上取整）二：基本的必要条件设图G=《V，E》是哈密顿图，则对于v的任意一个非空子集S，若以|S|表示S中元素的数目，G-S表示G中删除了S中的点以及这些点所关联的边后得到的子图，则W（G-S）《=|S|成立。
其中W（G-S）是G-S中联通分支数。
三：竞赛图（哈密顿通路）N（N》=2）阶竞赛图一点存在哈密顿通路。
算法：一：在Dirac定理的前提下构造哈密顿回路过程：1：任意找两个相邻的节点S和T，在其基础上扩展出一条尽量长的没有重复结点的路径。
即如果S与结点v相邻，而且v不在路径S -》T上，则可以把该路径变成v -》S -》T，然后v成为新的S.从S和T分别向两头扩展，直到无法继续扩展为止，即所有与S或T 相邻的节点都在路径S -》T上。
2：若S与T相邻，则路径S -》T形成了一个回路。
3：若S与T不相邻，可以构造出来一个回路。
设路径S -》T上有k+2个节点，依次为S，v1，v2，。
，vk，T.可以证明存在节点vi（i属于［1，k］），满足vi与T相邻，且vi+1与S相邻。
找到这个节点vi，把原路径变成S -》vi -》T -》vi+1 -》S，即形成了。
图论中的哈密尔顿回路与最短路径问题图论是离散数学的一个分支，研究的是图的性质及其在实际问题中的应用。
图是由节点（顶点）和边（边界）组成的集合，用来描述不同事物之间的关系或联系。
在图论中，有两个重要的问题：哈密尔顿回路和最短路径。
一、哈密尔顿回路哈密尔顿回路是指在无向图或有向图中，通过每个节点一次并且回到起点的路径。
在定义中并没有规定路径的长度，只要满足路径经过所有节点且回到起点即可。
哈密尔顿回路的存在性是一个经典的NP完全问题，即在多项式时间内无法求解。
判断一个图是否存在哈密尔顿回路需要遍历所有可能的路径，时间复杂度为O(n!)，其中n是图中节点数。
因此，对于大规模的图，求解哈密尔顿回路非常困难。
二、最短路径最短路径问题是指在图中找到两个节点之间的最短路径，即路径上的边权重之和最小。
最短路径有两种经典的算法：迪杰斯特拉算法和弗洛伊德算法。
1. 迪杰斯特拉算法迪杰斯特拉算法采用贪心策略，从起点开始逐步扩展最短路径的节点集合，直到找到目标节点或者扩展的节点集合为空。
具体步骤如下：1) 初始化起点到所有其他节点的距离为无穷大，起点到起点的距离为0。
2) 从起点开始，选择当前距离最短的节点，并将其加入最短路径的节点集合。
3) 更新当前节点周围节点的距离，如果新的路径更短，则更新距离。
4) 重复步骤2和3，直到找到目标节点或者最短路径的节点集合为空。
迪杰斯特拉算法的时间复杂度为O(n^2)，其中n是图中节点数。
2. 弗洛伊德算法弗洛伊德算法采用动态规划的思想，通过中间节点更新两个节点之间的距离，直到求解出所有节点之间的最短路径。
具体步骤如下：1) 初始化节点之间的距离，如果两个节点直接相邻，则设置距离为边的权重，否则设置距离为无穷大。
2) 对于每一对节点i和j，选择中间节点k，并更新节点i和节点j之间的距离，如果经过节点k的路径更短则更新距离。
3) 重复步骤2，直到求解出所有节点之间的最短路径。
弗洛伊德算法的时间复杂度为O(n^3)，其中n是图中节点数。
哈密顿算法遍历哈密顿算法是一种常用于图论中的遍历算法，用于寻找图中的哈密顿路径或哈密顿回路。
哈密顿路径是指一个无向图中通过每个顶点一次且仅一次的路径，而哈密顿回路则是指一个无向图中通过每个顶点一次且仅一次的闭合路径。
该算法的实现原理是通过深度优先搜索（DFS）来遍历图中的所有可能路径，在每个顶点上进行回溯，直到找到满足条件的哈密顿路径或回路。
下面将详细介绍哈密顿算法的遍历流程和关键步骤。
1.首先，确定起始顶点。
在哈密顿算法中，起始顶点对结果并不产生影响，因为哈密顿路径或回路可以从任意顶点开始。
因此，选择任意一个顶点作为起点，将其标记为已访问。
2.接下来，进入递归回溯的过程。
从起点开始，选择一个邻接顶点作为下一个访问的节点，并将其标记为已访问。
然后，继续对该邻接顶点进行递归回溯，直到满足下面两个终止条件之一：- 所有的顶点都已经访问过，即构成了一条哈密顿路径或回路。
- 当前深度已经达到图中的总顶点数，但没有形成哈密顿路径或回路。
3.在进行递归回溯时，需要做以下判断：- 判断当前顶点是否为未访问过的顶点，如果是，则选择该顶点作为下一个访问节点，并标记为已访问。
- 判断当前顶点是否与起始顶点相邻，如果是，则判断是否满足哈密顿回路的条件，即所有顶点都已经访问过。
如果是，则输出该路径或回路。
- 判断当前顶点是否与起始顶点不相邻，如果是，则判断是否满足哈密顿路径的条件，即所有顶点都已经访问过。
如果是，则输出该路径。
4.若当前顶点的邻接顶点都已经访问过，或者当前深度已经达到图中的总顶点数，但没有形成哈密顿路径或回路，则进行回溯。
回溯时，将当前顶点重新标记为未访问，并返回上一层递归。
通过以上步骤，可以使用哈密顿算法来遍历图中的所有可能的哈密顿路径或回路。
在实际应用中，哈密顿算法可以用于解决旅行推销员问题、电路布线问题等，具有重要的实际意义。
总结起来，哈密顿算法遍历的核心思想是通过深度优先搜索来枚举图中的所有路径，并进行回溯来寻找满足哈密顿路径或回路的条件。
图论中的最长路径问题与最短路径问题在图论中，最长路径问题和最短路径问题是两个重要且常见的问题。
最长路径问题旨在寻找图中两个顶点之间的最长路径，而最短路径问题则是寻找图中两个顶点之间的最短路径。
本文将分别介绍这两个问题，并讨论它们的应用和解决方法。
首先，我们来讨论最长路径问题。
最长路径问题在实际应用中有着广泛的应用，例如交通规划、通信网络以及电路设计等。
在图中，路径是由一系列顶点连接而成的。
最长路径问题的目标是找到两个顶点之间的路径中具有最大权值的路径。
最长路径问题可以通过深度优先搜索（DFS）算法来解决。
深度优先搜索是一种用于遍历或搜索图的算法，它从一个顶点开始，沿着路径尽可能地往下搜索，直到达到无法再继续搜索的顶点为止。
在深度优先搜索的过程中，我们可以记录下每个顶点的最大路径长度，最终找到两个顶点之间的最长路径。
接下来，我们将讨论最短路径问题。
最短路径问题在实际应用中同样具有重要性，例如导航系统、网络路由以及货物运输等。
最短路径问题的目标是找到两个顶点之间的路径中具有最小权值之和的路径。
最短路径问题可以通过使用迪杰斯特拉算法（Dijkstra algorithm）来解决。
迪杰斯特拉算法是一种用于解决单源最短路径问题的贪婪算法。
它从一个起始顶点开始，逐步地计算到达其他顶点的最短路径长度。
通过不断更新路径长度，并选择当前路径长度最小的顶点进行下一步计算，最终可以确定出起始顶点到其他顶点的最短路径。
最长路径问题和最短路径问题在实际应用中有着广泛的应用。
最长路径问题可以帮助我们优化电路设计，提高通信网络的稳定性，也可以提供交通规划的参考。
而最短路径问题可以帮助我们制定最优的导航路线，提高货物运输的效率，也可以优化网络路由的选择。
综上所述，最长路径问题和最短路径问题是图论中两个重要的问题。
通过深度优先搜索和迪杰斯特拉算法，我们可以解决这两个问题，并在实际应用中获得丰富的应用场景。
无论是最长路径问题还是最短路径问题，它们都展示了图论在实际生活中的重要性和广泛的应用前景。
哈密尔顿环c算法
哈密尔顿环问题是图论中的一个经典问题，它要求在给定的图中找到一个包含图中所有顶点的环路，这个环路被称为哈密尔顿环。
哈密尔顿环问题是一个NP完全问题，意味着在一般情况下，没有已知的有效算法能够在多项式时间内解决这个问题。
在解决哈密尔顿环问题时，常常会使用 C 语言实现各种算法。
下面是一些常见的用于解决哈密尔顿环问题的算法：
一、回溯法：这是最常用的解决哈密尔顿环问题的方法之一。
回溯法通过尝试所有可能的顶点排列顺序，并使用剪枝技术来减少搜索空间，以找到一个哈密尔顿环。
二、分支定界法：这是一种优化的回溯法，通过将搜索空间划分为更小的子空间，并使用剪枝技术来减少搜索空间。
分支定界法通常比简单的回溯法更高效。
三、动态规划：动态规划方法通过将问题划分为子问题，并利用子问题的解来求解原始问题。
然而，在实践中，动态规划方法通常用于解决某些特定类型的图，而不是一般的图。
四、启发式算法：启发式算法通过一系列的规则和启发式方法来搜索哈密尔顿环。
这些算法可能不保证找到最优解，但是在实践中通常能够在较短的时间内找到一个较好的解。
总的来说，解决哈密尔顿环问题的算法通常是复杂的，并且通常需要在给定问题的特定条件下进行调整和优化。
C 算法通常是一种常见的实现方式，用于解决这个问题。
图论中的最长路径问题与最短路径问题图论是数学中研究图的理论，其中最长路径问题和最短路径问题是图论中的经典问题。
本文将介绍这两个问题的定义、求解方法以及应用领域。
一、最长路径问题最长路径问题是指在给定的图中寻找一条路径，使得该路径的长度在所有路径中最长。
路径的长度可以根据边或顶点的数量来计算。
解决最长路径问题的方法有多种，其中最常用的是动态规划算法。
动态规划是一种将问题分解为子问题并逐步解决的算法。
在最长路径问题中，动态规划算法通常通过求解顶点的最长路径长度来得到整个图的最长路径。
在应用中，最长路径问题可以用来解决实际生活中的许多问题，例如交通规划、物流路径优化等。
通过找到最长路径，可以使得交通系统更加高效，减少行程时间和成本。
二、最短路径问题最短路径问题是指在给定的图中寻找一条路径，使得该路径的长度在所有路径中最短。
路径的长度可以根据边或顶点的权重来计算。
解决最短路径问题的方法同样有多种，其中最著名的是Dijkstra算法和Floyd-Warshall算法。
Dijkstra算法是一种贪婪算法，用于解决单源最短路径问题；Floyd-Warshall算法是一种动态规划算法，用于解决所有顶点对之间的最短路径问题。
最短路径问题在现实生活中有广泛应用，例如导航系统、网络路由等。
通过找到最短路径，可以计算出最佳的行进方向，使得路程更加迅捷和经济。
三、最长路径问题与最短路径问题的联系与区别最长路径问题和最短路径问题都是求解图中不同路径的问题，但两者在定义和目标上有所不同。
最长路径问题试图找到一条路径，使得其长度最大化，而最短路径问题试图找到一条路径，使得其长度最小化。
最长路径问题通常通过动态规划算法求解，而最短路径问题则可以通过Dijkstra算法和Floyd-Warshall算法等多种方法解决。
最长路径问题和最短路径问题在应用中也有差异。
最长路径问题主要应用于交通规划、物流路径优化等领域，而最短路径问题则广泛应用于导航系统、网络路由等领域。
Algorithm Design TechniquesAssignment3:Solutions(1)Hamiltonian Path.(a)Longest Path ProblemThe Longest Path Problem is in NP.Given a solution path P,we justcheck that P consists of at least k edges,and that these edges form apath(where no vertex is used more than once).This verification can bedone in polynomial time.The reduction follows directly from Hamiltonian Path.Given an instanceof Hamiltonian Path on a graph G=(V,E).We create an instance of thelongest path problem G ,k as follows.We use exactly the same graph,i.e G =G and we set k=|V|−1.Then there exists a simple path oflength k in G iffG contains a Hamiltonian path.(b)Minimum Leaf Spanning treeThe Minimum Leaf Spanning tree is in NP.Clearly the certificate is atree of k leaves,which can be verified in linear time.Again,the reduction follows directly from Hamiltonian Path.Given aninstance of Hamiltonian Path on a graph G=(V,E).We create an in-stance of the minimum leaf spanning tree problem G ,k as follows.Again,we use exactly the same graph,i.e G =G but now we set k=2.A treewith2leaves is a path,so a spanning tree with two leaves is a Hamilton-ian Path in the graph.So there exists a Hamiltonian path iffthere existsa spanning tree with2leaves.(2)Hitting Set Problem.The Hitting Set problem is in NP.To check a solution a∗1,...,a∗kwe just seeif every set B j is hit by at least one of the a∗i.We use a reduction from Set Cover to show NP-completeness.Given sets S1,...,S n and a ground set W={w1,...,w m}of elements to cover,let a1,...,a n represent the sets and let B1,...,B m represent the elements.We say that a i hits B j if and only if set S i contains element w j.It follows that12there is a hitting set of size at most k if and only if there is a set cover of size at most k .This is a polynomial reduction.We use a reduction from Partition to show NP-completeness.We have inte-gers x 1,...,x n and we want to find a subset S ⊂[n ]with i ∈S x i = i/∈S x i .To set this up as a zero-weight cycle problem we take a directed cycle with n arcs,one for each integer.We now make two copies of each arc i .One copy has weight x i and the other has weight −x i .So any directed cycle in G uses exactly one the type i arcs.Let S be the set of integers where we use their positive arcs.Thus the weight of the corresponding cycle is i ∈S x i − i/∈S x i .Clearly,this equals zero if and only if we have the desired partition.This is a polynomial reduction.(3)Dominating Set.Dominating Set is in NP.To check a proposed solution S ⊂V ,we simply have to check that any vertex not in S is adjacent to some vertex in S .We use a reduction from Set Cover to show NP-completeness.Given sets S 1,...,S n and a ground set W ={w 1,...,w m }of elements to cover,we create a graph as follows.There is a vertex v i for each set S i and a vertex u j for each element w j .There is an edge (v i ,w j )if and only if w j is in set S i .Finally we add an edge (v i ,v i )for each pair of sets S i and S j -we do this because then every v i are more useful than any u j in building a dominating set.It is then easy to see that there is a dominating set of size at most k in G if and only if there is a set cover of size at most k .This is a polynomial reduction.(4)Feedback vertex set.The Feedback vertex set problem is in NP.To check a proposed solution,X ⊆V ,we just verify that G −X forms an acyclic graph.This verification can be done in polynomial time.We use a reduction from Vertex Cover problem to show NP-Completeness.Take an instance of vertex cover in an undirected graph G U =(V ,E ).We now replace each edge in the undirected graph with two directed edges,a for-ward edge and a backward edge to obtain the directed graph,G D =(V ,A ).So we now need to prove that,X ⊆V is a vertex cover in G U iffX forms a feedback vertex set in G D .Assume X is a vertex cover of G U .Then by definition,every edge of G U must be incident with at least one vertex of X .Clearly,every directed edge3of G D should also be incident with at least one vertex of X .So every cycle in G D must include a vertex of X .Now,assume that X is a feedback vertex set of the directed graph G D .Then by definition,every cycle in G D must include a vertex of X .Consider any cycle of length 2.This is just a pair of directed edges between two vertices.So X must contain at least one vertex for each cycle of length 2in G D .But,by our construction,for every edge in G U joining two vertices,G D contains a cycle of length 2between the same pair of vertices.So X contains at least one of these two vertices for each edge in G U .So X is a vertex cover of G U .(5)Bartering.This problem is in NP.To check a feasible exchange of subset S of items of player I and subset T of items of player II,we simply check that I prefers T to S and II prefers S to T .We use a reduction from the Knapsack problem to show NP-completeness.We have n items of weights w 1,...,w n and values v 1,...,v n :Is there a set of items of weight at most W and value at least V .We set up a barter economy with just 2people.Person I has n items that she values at w 1,...,w n ;Person II values these items at v 1,...,v n .Person II has just one item that he values at V −1;Person I values this item at W +1.So a trade can take place if I has a subset of item of weight at most W and that has a value of at least V .This is a polynomial reduction.(6)Galactic Shortest Paths.This problem is in NP.To check a proposed path P ,we just check that it has length at most L and risk value at most R .We use a reduction from Partition to show NP-completeness.Again,we have integers x 1,...,x n and we want to find a subset S ⊂[n ]with i ∈S x i = i/∈S x i .To set this up as a path problem we take a directed path (with end vertices s and t )with n arcs,one for each integer.We now make two copies of each arc i .The first copy has length x i and risk value 0;the second copy has length 0and risk value x i .So any s −t path P in G uses exactly one the type i arcs.Let S be the set of integers where we use their first copy.Thus the length of the path is i ∈S x i ;the risk of this path is risk values on those integers where we use the second copy of their arcs,so the risk is i/∈S x i .So set R =L =12i x i .Then we have a path of length at most L and risk at most R if an only if we have a valid partition.This is a polynomial reduction.。
T-79.5103Computational Complexity Theory,Autumn2011Tutorial41(8) Problem1LetΣbe afixed alphabet.A codingκis defined to be a mapping fromΣtoΣ(κis not necessarily one-to-one).For a string x=x1x2···x n∈Σ∗, defineκ(x)=κ(x1)κ(x2)···κ(x n).If L⊆Σ∗is a language,defineκ(L)= {κ(x)|x∈L}.Without loss of generality we also assume that the Turing machine specific symbols and are mapped to themselves and no other symbol is mapped to them.The goal is to show that NP is closed under codings,that is,if L∈NP is a language andκis a coding,thenκ(L)∈NP.A ProofLetκ:Σ→Σbe a coding and L∈NP a language.Now let M= K,Σ,∆,s be a non-deterministic Turing machine deciding L in polynomial time(since L∈NP,one must exist).We now construct a non-deterministicTuring machine M decidingκ(L)as follows.Given an input x =x1x2...xn,M first non-deterministically guesses a string x=x1x2...x n and then de-terministically checks thatκ(x)=x (remember that the coding is given). The machine M then executes M on x as a subroutine and says“yes”(“no”) iffM says so.Clearly,if there is a string x∈L such thatκ(x)=x ,then and only then M accepts x .Therefore M accepts x iffx ∈κ(L).Since M runs in(non-deterministic)polynomial time,κ(L)∈NP.Thus NP is closed under codings.A Non-ProofTo learn a lesson,we show a construction that does not work.Letκ:Σ→Σbe a coding and L∈NP a language.Now let M= K,Σ,∆,s be a non-deterministic Turing machine deciding L in polynomial time(since L∈NP,one must exist).Define the non-deterministic Turing machine M = K,Σ,∆ ,s such that q,σ,q ,ρ,D ∈∆⇔ q,κ(σ),q ,κ(ρ),D ∈∆ . That is,we choose M to be the“coding”of the machine M.First,the following can be shown by a simple inductive argument on the length of the computation:If the input for M is x and the input for M is κ(x),then if M can perform a transition sequences,σ,q1,ρ1,d1 q1,ρ1,q2,ρ2,d2 ··· q n−1,ρn−1,q n,ρn,d nT-79.5103Computational Complexity Theory,Autumn2011Tutorial42(8)ending in configuration q n,w,u ,then M can perform the sequences,κ(σ),q1,κ(ρ1),d1 q1,κ(ρ1),q2,κ(ρ2),d2 ··· q n−1,κ(ρn−1),q n,κ(ρn),d n of transitions ending in configuration q n,κ(w),κ(u) .That is,if for an input x there is a computation of M ending in“yes”state,then for the inputκ(x) there is a computation of M ending in“yes”state.Therefore,L(M )⊇κ(L). However,the converse does not necessarily hold.It may be possible that for an input˜x=˜x1...˜x n the machine M can perform a sequences,˜σ,q1,˜ρ1,d1 ··· q n−1,˜ρn−1,q n,˜ρn,d nof transitions ending in configuration q n,˜w,˜u ,while there is no input x= x1...x n such thatκ(x)=˜x for which the machine M can perform a sequence s,σ,q1,ρ1,d1 ... q n−1,ρn−1,q n,ρn,d nof transitions ending in configuration q n,w,u such that˜σ=κ(σ),˜ρi=κ(ρi) for all1≤i≤n,˜w=κ(w)and˜u=κ(u).For instance,letM= K={p,q},Σ={a,b},∆={(p,a,q,b,−),(q,a,“yes”,a,−)},p and letκ={a→a,b→a}.NowM = K={p,q},Σ={a,b},∆ ={(p,a,q,a,−),(q,a,“yes”,a,−)},p . It is quite clear that M cannot enter the“yes”state on any input and thus L=L(M)=∅.However,with any input beginning with a,M enters its“yes”state after two steps.Thus L(M )=a∗,which does not equal to κ(L)=∅.To sum up,although L(M )⊇κ(L),sometimes it possible that L(M )⊃κ(L)and therefore L(M )=κ(L).Problem2PreliminariesThe reduction technique revisited:a way to show that a problem is NP-complete.Assume a problem(a language)PROB that we wish to show to be NP-complete.First,we have to show that PROB is in NP,i.e.,that there is a non-deterministic Turing machine deciding whether an arbitrary input string belongs to PROB in polynomial time.Second,we show that PROBT-79.5103Computational Complexity Theory,Autumn2011Tutorial43(8)is NP-hard by the following technique:We take a problem that is known to be NP-complete,such as SAT or CLIQUE,and reduce it to PROB.The reduction is a log-space computable function that maps each instance of the chosen NP-complete problem into an instance of PROB in a way that the original instance is a“yes”-instance of the chosen NP-complete problem if and only if the mapped instance is a“yes”-instance of PROB.A Proof that LONGEST PATH is NP-completeThe problem LONGEST PATH is:Given an undirected graph G= V,E and a positive(binary coded)integer K≤|V|,does G have a simple path (that is,a path encountering no vertex more than once)with K or more edges?We use a simple reduction from HAMILTON PATH problem:Given an undirected graph,does it have a Hamilton path,i.e.,a path visiting each vertex exactly once?HAMILTON PATH is NP-comple(page193in the book).Given an instance G = V ,E for HAMILTON PATH,count the number|V |of nodes in G and output the instance G=G ,K=|V |for LONGEST PATH.Obviously,G has a simple path of length|V |if and only if G has a Hamilton path.Furthermore,consider the following variant of LONGEST PATH:Given an undirected graph G= V,E ,two vertices v,v ∈V,and a positive(bi-nary coded)integer K≤|V|,does G have a simple path(that is,a path encountering no vertex more than once)with K or more edges from v to v ?We can use the same reduction from HAMILTON PATH BETWEEN TWO VERTICES problem:Given an undirected graph and two of its ver-tices,does it have a Hamiton path between the given vertices?It is known that HAMILTON PATH BETWEEN TWO VERTICES is NP-complete, see,e.g.,Garey and Johnson:“Computers and Intractability–A Guide to the Theory of NP-Completeness”.Demonstration problemsProblem1continuedShow that P is closed under codings if and only if P=NP.T-79.5103Computational Complexity Theory,Autumn2011Tutorial44(8)If P=NP,then by the previous result P is closed under codings.Now let L be the language such that each string in L consists of1.a Boolean expression represented as in page77of the book,and2.a truth valuation for the expression satisfying it.However,the val-uation is expressed by using extra symbols x ,0 ,1 ,,,=,true ,false which do not occur in the representation of the expression.The parts are separated with’;’.For instance,(x1∧¬x2)∨x3;x 1 =true ,x 2 =false ,x 3 =falseis a string in L(numbers are presented in binary of same length,e.g.3 ≡1 0 and1≡01).The corresponding problem SAT CHECKING,“Given a Boolean expression and a truth valuation for it,does the truth valuation satisfy the expression”is clearly in P,i.e.,L can be decided in deterministic polynomial time.Now take a codingκmapping the symbols x ,0 ,1 ,,,= ,true and false to a pseudo blank symbol ,keeping other symbols intact. Nowκ(L)is the set of all satisfiable Boolean expressions(each augmented with v×(1+ log v +2)pseudo blanks where v is the number of variables in the expression),i.e.,κ(L)is the SAT problem.If P were closed under coding,then there would be a deterministic polynomial time Turing machine decidingκ(L)and thus SAT would be in P.Since all the problems in NP are reducible in polynomial time(by using log-space reductions)to SAT(SAT is NP-complete),this would imply that all the problems in NP are solvable in polynomial time and P=NP.We conclude that P is closed under codings if and only if P=NP.A proof that HORNSAT is P-completeA clause l1∨l2∨···∨l n,where l1,...,l n are literals,is a Horn clause if it has at most one positive literal(page78in Papadimitriou’s book).Furthermore, we know that the problem HORNSAT,asking whether a conjunctive normal form(CNF)Boolean expression consisting only of Horn clauses is satisfiable, is in P(page79).A language L in a complexity class C is C-complete(under log-space reduc-tions)if any language L ∈C can be reduced(in log-space)to L.And,if L is C-complete and L reduces to a language L ∈C,then L is also C-complete.T-79.5103Computational Complexity Theory,Autumn 2011Tutorial 45(8)Theorem 1HORNSAT is P -complete under log-space reductions.Proof.First,as mentioned above,HORNSAT is in P .We now reduce MONOTONE CIRCUIT VALUE,that we know to be P -complete (page 171in the book),to HORNSAT and in this way show that HORNSAT is P -complete.Let C =(V ={v 1,...,v n },E )be a monotone,variable-free Boolean circuit.Thus each gate of C is of sort ∧,∨,true or false ,and the answer to MONO-TONE CIRCUIT VALUE is “yes”if and only if the output gate of the circuit C evaluates to true .We now construct a conjunction f (C )of Horn clauses (i.e.,a Boolean expression f (C )in Horn CNF)such that f (C )is satisfiable if and only if the output gate of the circuit C evaluates to true .We first con-vert C into a Horn CNF Boolean expression ˜f (C )= v ∈V C v over variables ˆv 1,...,ˆv n corresponding to the gates v 1,...,v n of C .The intuitive meaning of a variable ˆv i is that it denotes that a gate v i evaluates to false in C .˜f (C )is defined as follows:•If the sort of the gate v ,denoted by s (v ),is ∨and v ,v are the children of v ,then C v is (ˆv ∧ˆv )⇒ˆv equaling to the Horn clause ¬ˆv ∨¬ˆv ∨ˆv .That is,if both of children evaluate to false,then so should the gate itself.•If s (v )=∧and v ,v are the children of v ,then C v is (ˆv ⇒ˆv )∧(ˆv ⇒ˆv )equaling to (¬ˆv ∨ˆv )∧(¬ˆv ∨ˆv ).The idea is that if either of the children is false,then the gate should also be.•If s (v )=true ,then C v is ¬ˆv .•If s (v )=false ,then C v is ˆv .Note that the construction of ˜f(C )is NOT exact.For instance,if v is an ∧-gate with its children v and v assigned to true (i.e.,ˆv and ˆv are assigned to be false),then the variable ˆv corresponding to the gate v can have either of the values true or false since the clauses (¬ˆv ∨ˆv )∧(¬ˆv ∨ˆv ).are already satisfied.BUT,if ˆv and ˆv are assigned to be true (i.e.,gates v and v evaluate to false),then ˆv MUST be true (v evaluates to false).We formalize this in the following.Lemma 2If a gate v of C evaluates to false in C ,then all satisfying truth assignments for ˜f (C )must assign the variable ˆv to true .T-79.5103Computational Complexity Theory,Autumn2011Tutorial46(8)Proof.By induction on the structure of C.Induction base:For a constant input gate with s(v)=true the lemma holds trivially because v cannot evaluate to false.If v is an a constant input gate with s(v)=false,then the clauseˆv is in˜f(C)and the lemma clearly holds. Induction hypothesis:Assume a sub-sircuit C of C for which the lemma holds.C is assumed to be closed under the children-relation,i.e.if a gate v is in C ,then its children are in C ,too.Induction step:Consider a gate v of C not in C such that the children of v, v and v ,belong to C .Let C be the sub-circuit otherwise similar to C but augmented with v and let˜f(C )be the corresponding Horn CNF formula. Now there are two cases depending on the sort of v:1.Assume that v is a∨-gate.If v evaluates to false in C ,then bothv and v must evaluate to false in C and in C .By the induction hypothesis,it must be thatˆv andˆv are assigned to true in any satisfying truth assignment for˜f(C ).Thusˆv must be assigned to true in any satisfying truth assignment for˜f(C )=(¬ˆv ∨¬ˆv ∨ˆv)∧˜f(C ).2.Assume that v is a∧-gate.If v evaluates to false in C ,then v or vevaluates false in C and in C .By the induction hypothesis,it must be thatˆv orˆv is assigned to true in any satisfying truth assignment for˜f(C ).Thusˆv must be assigned to true in any satisfying truth assignment for˜f(C )=(¬ˆv ∨ˆv)∧(¬ˆv ∨ˆv)∧˜f(C ).Lemma3The truth assignment forˆv1,...,ˆv n that assignsˆv i to true(false) if and only if v evaluates to false(true)in C,satisfies˜f(C).Proof.By inspecting all the clauses in˜f(C).1.Case s(v)=∨and v ,v are the children of v.If either v or v evaluates to true,then(i)v evaluates to true,(ii) eitherˆv orˆv is assigned to false,(iii)ˆv is assigned to false,and(iv) the clause C v=¬ˆv ∨¬ˆv ∨ˆv is satisfied.If both v and v evaluate to false,then(i)v evaluates to false,(ii)ˆv,ˆv andˆv are assigned to true,and(iii)the clause C v=¬ˆv ∨¬ˆv ∨ˆv is satisfied.T-79.5103Computational Complexity Theory,Autumn2011Tutorial47(8)2.Case s(v)=∧and v ,v are the children of v.If both v and v evaluate to true,then(i)v evaluates to true,(ii)ˆv,ˆv andˆv are assigned to false,and(iii)the clauses in C v=(¬ˆv ∨ˆv)∧(¬ˆv ∨ˆv)are satisfied.If either v or v evaluates to false,then(i)v evaluates to false,(ii) eitherˆv orˆv is assigned to true,(iii)ˆv is assigned to true,and(iv) the clauses in C v=(¬ˆv ∨ˆv)∧(¬ˆv ∨ˆv)are satisfied.3.Case s(v)=true.Now v evaluates to true,ˆv is assigned to false,andthe clause C v=¬ˆv is satisfied.4.Case s(v)=false.Now v evaluates to false,ˆv is assigned to true,andthe clause C v=ˆv is satisfied.As a consequence of the two lemmas above,we have the following. Theorem4The output gate v1of C evaluates to true if and only if there is a satisfying truth assignment for˜f(C)assigning the variableˆv1to false. Now we form f(C)from˜f(C)by adding an extra Horn clause¬ˆv1for the output gate v1of C.It is a clear consequence of the theorem above that the output gate v1of C evaluates to true if and only if f(C)has a satisfying truth assignment.We have therefore mapped an object C to an object f(C) such that C is in MONOTONE CIRCUIT VALUE ifff(C)is in HORNSAT. It remains to show that this reduction from a circuit C to a Horn CNF formula f(C)can be done by using space O(log n).Assume that the input format for C is of form g1;g2;...;g n;,where each g i is either vi=vj∨vk, vi=vj∧vk,vi= (for true gates)or vi=⊥(for false gates),and the numbers1≤i,j,k≤n=|V|are coded in binary by using symbols0and1. Now the reduction can be carried out by using three“registers”(tapes or tape positions)i,j,k,each of which is of logarithmic size w.r.t.the representation of C and a constant size register for the sort of the current gate definition g i scanned.The reduction machine scans the g i s of the input one at the time, saving the indices i,j,k and the sort of the gate(∨,∧,true or false)to the corresponding registers.It then writes the above mentioned(constant size) Horn clauses corresponding to the scanned g i into the output tape.Thus the reduction can clearly be performed in logarithmic space.T-79.5103Computational Complexity Theory,Autumn2011Tutorial48(8) A Proof that MAX2SAT is NP-completeSee pages186–187in the book.A Proof that INDEPENDENT SET is NP-complete See pages188–189in the book.。
