chap36.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<h2>A formal-language framework</h2><P>
<a name="09fe_1c84"><a name="09fe_1c85"><a name="09fe_1c86"><a name="09fe_1c87">One of the convenient aspects of focusing on decision problems is that they make it easy to use the machinery of formal-language theory. It is worthwhile at this point to review some definitions from that theory. An <I><B>alphabet</I></B> <img src="../images/sum14.gif"> is a finite set of symbols. A <I><B>language</I></B><I> L</I> over <img src="../images/sum14.gif"> is any set of strings made up of symbols from <img src="../images/sum14.gif">. For example, if <img src="../images/sum14.gif"> = {0, 1}, the set <I>L</I> = {10, 11, 101, 111, 1011, 1101, 10001, . . .} is the language of binary representations of prime numbers. We denote the <I><B>empty string</I></B> by <img src="../images/epsilon.gif">, and the <I><B>empty language</I></B> by <img src="921_a.gif">. The language of all strings over <img src="../images/sum14.gif"> is denoted <img src="../images/sum14.gif">*. For example, if <img src="../images/sum14.gif"> = {0, 1}, then <img src="../images/sum14.gif">* = {<img src="../images/epsilon.gif">, 0, 1, 00, 01, 10, 11, 000, . . .} is the set of all binary strings. Every language <I>L</I> over <img src="../images/sum14.gif"> is a subset of <img src="../images/sum14.gif">*.<P>
<a name="09fe_1c88"><a name="09fe_1c89"><a name="09fe_1c8a"><a name="09fe_1c8b">There are a variety of operations on languages. Set-theoretic operations, such as <I><B>union</I></B> and <I><B>intersection</I></B>, follow directly from the set-theoretic definitions. We define the <I><B>complement</I></B> of <I>L</I> by <img src="921_b.gif">. The <I><B>concatenation </I></B>of two languages<I> L</I><SUB>1</SUB> and <I>L</I><SUB>2</SUB> is the language<P>
<pre><I>L</I> = {<I>x</I><SUB>1</SUB><I>x</I><SUB>2</SUB> : <I>x</I><SUB>1</SUB> <img src="../images/memof12.gif"> <I>L</I><SUB>1</SUB> and <I>x</I><SUB>2</SUB> <img src="../images/memof12.gif"> <I>L</I><SUB>2</SUB>} .</sub></sup></pre><P>
<a name="09fe_1c8c"><a name="09fe_1c8d"><a name="09fe_1c8e">The<B> </B><I><B>closure</I></B> or <I><B>Kleene star</I></B> of a language <I>L</I> is the language<P>
<pre><I>L</I><SUP>*</SUP> = {<img src="../images/epsilon.gif">} <img src="../images/wideu.gif"> <I>L</I> <img src="../images/wideu.gif"> <I>L</I><SUP>2</SUP> <img src="../images/wideu.gif"><I>L</I><SUP>3</SUP> <img src="../images/wideu.gif"> <SUP> . . </SUP> ,</sub></sup></pre><P>
where <I>L<SUP>k</I></SUP> is the language obtained by concatenating <I>L</I> to itself <I>k</I> times.<P>
From the point of view of language theory, the set of instances for any decision problem <I>Q</I> is simply the set <img src="../images/sum14.gif">*, where <img src="../images/sum14.gif"> = {0, 1}. Since <I>Q</I> is entirely characterized by those problem instances that produce a 1 (yes) answer, we can view <I>Q</I> as a language <I>L</I> over <img src="../images/sum14.gif"> = {0, 1}, where<P>
<pre><I>L</I> = {<I>x</I> <img src="../images/memof12.gif"> <img src="../images/sum14.gif">* : <I>Q</I>(<I>x</I>) = 1} .</sub></sup></pre><P>
For example, the decision problem PATH has the corresponding language<P>
<pre><a name="09fe_1c8f">PATH = {<img src="../images/lftwdchv.gif"><I>G,u,v,k</I><img src="../images/wdrtchv.gif"><I> : G</I> = (<I>V,E</I>) is an undirected graph,</sub></sup></pre><P>
<pre><I>u</I>,<I>v</I> <img src="../images/memof12.gif"> <I>V</I>,</sub></sup></pre><P>
<pre><I>k</I> <img src="../images/gteq.gif"> 0 is an integer, and</sub></sup></pre><P>
<pre>there exists a path from <I>u</I> to <I>v</I> in <I>G</I></sub></sup></pre><P>
<pre>whose length is at most <I>k</I>}.</sub></sup></pre><P>
(Where convenient, we shall sometimes use the same name--PATH in this case--to refer to both a decision problem and its corresponding language.) <P>
<a name="09fe_1c90"><a name="09fe_1c91"><a name="09fe_1c92">The formal-language framework allows us to express the relation between decision problems and algorithms that solve them concisely. We say that an algorithm A <I><B>accepts </I></B>a string<I> x</I> <img src="../images/memof12.gif"> {0, 1}* if, given input <I>x</I>, the algorithm outputs <I>A</I>(<I>x</I>) = 1. The language<B> </B><I><B>accepted</I></B> by an algorithm <I>A</I> is the set <I>L</I> = {<I>x</I> <img src="../images/memof12.gif"> {0, 1}* :  <I>A</I>(<I>x</I>) = 1}, that is, the set of strings that the algorithm accepts. An algorithm <I>A <B>rejects</I></B> a string <I>x</I> if <I>A</I>(<I>x</I>) = 0.<P>
<a name="09fe_1c93"><a name="09fe_1c94">Even if language <I>L</I> is accepted by an algorithm <I>A</I>, the algorithm will not necessarily reject a string <I>x</I> <img src="../images/notmem.gif"> <I>L</I> provided as input to it. For example, the algorithm may loop forever. A language <I>L</I> is <I><B>decided</I></B> by an algorithm <I>A</I> if every binary string is either accepted or rejected by the algorithm. A language <I>L</I> is <I><B>accepted in polynomial time</I></B> by an algorithm <I>A</I> if for any length-<I>n</I> string <I>x</I> <img src="../images/memof12.gif"> <I>L</I>, the algorithm accepts <I>x</I> in time <I>O</I>(<I>n<SUP>k</I></SUP>) for some constant <I>k</I>. A language <I>L</I> is <I><B>decided in polynomial time</I></B> by an algorithm <I>A</I> if for any length-<I>n</I> string <I>x</I> <img src="../images/memof12.gif">{0, 1 }*, the algorithm decides <I>x</I> in time <I>O</I>(<I>n<SUP>k</I></SUP>) for some constant <I>k</I>. Thus, to accept a language, an algorithm need only worry about strings in <I>L</I>, but to decide a language, it must accept or reject every string in {0, 1}*.<P>
As an example, the language PATH can be accepted in polynomial time. One polynomial-time accepting algorithm computes the shortest path from <I>u</I> to <I>v</I> in <I>G</I>, using breadth-first search, and then compares the distance obtained with <I>k</I>. If the distance is at most <I>k</I>, the algorithm outputs 1 and halts. Otherwise, the algorithm runs forever. This algorithm does not decide PATH, however, since it does not explicitly output 0 for instances in which the shortest path has length greater than <I>k</I>. A decision algorithm for PATH must explicitly reject binary strings that do not belong to PATH. For a decision problem such as PATH, such a decision algorithm is easy to design. For other problems, such as Turing's Halting Problem, there exists an accepting algorithm, but no decision algorithm exists.<P>
<a name="09fe_1c95"><a name="09fe_1c96"><a name="09fe_1c97"><a name="09fe_1c98">We can informally define a <I><B>complexity class</I></B> as a set of languages, membership in which is determined by a <I><B>complexity measure</I></B>, such as running time, on an algorithm that determines whether a given string <I>x</I> belongs to language <I>L</I>. The actual definition of a complexity class is somewhat more technical--the interested reader is referred to the seminal paper by Hartmanis and Stearns [95].<P>
Using this language-theoretic framework, wee can provide an alternative definition of the complexity class P:<P>
<pre>P = {<I>L</I> <img src="../images/rgtubar.gif"> {0,1}* : there exists an algorithm <I>A</I></sub></sup></pre><P>
<pre>that decides <I>L</I> in polynomial time} .</sub></sup></pre><P>
In fact, P is also the class of languages that can be accepted in polynomial time.<P>
<a name="09fe_1c99">Theorem 36.2<a name="09fe_1c99"><P>
P = {<I>L : L </I>is accepted by a polynomial-time algorithm}<I> .</I><P>
<I><B>Proof</I></B>     Since the class of languages decided by polynomial-time algorithms is a subset of the class of languages accepted by polynomial-time algorithms, we need only show that if <I>L</I> is accepted by a polynomial-time algorithm, it is decided by a polynomial-time algorithm. Let <I>L</I> be the language accepted by some polynomial-time algorithm <I>A</I>. We shall use a classic "simulation" argument to construct another polynomial-time algorithm <I>A</I>' that decides <I>L</I>. Because <I>A</I> accepts <I>L</I> in time <I>O</I>(<I>n<SUP>k</I></SUP>) for some constant <I>k</I>, there also exists a constant <I>c</I> such that <I>A</I> accepts <I>L </I>in at most<I> T</I> = <I>cn<SUP>k</I></SUP> steps. For any input string <I>x</I>, the algorithm <I>A</I>' simulates the action of <I>A</I> for time <I>T</I>. At the end of time <I>T</I>, algorithm <I>A</I>' inspects the behavior of <I>A</I>. If <I>A</I> has accepted <I>x</I>, then <I>A</I>' accepts <I>x</I> by outputting a 1. If<I> A</I> has not accepted <I>x</I>, then <I>A</I>' rejects <I>x</I> by outputting a 0. The overhead of <I>A</I>' simulating <I>A</I> does not increase the running time by more than a polynomial factor, and thus <I>A</I>' is a polynomial-time algorithm that decides <I>L.     </I> <P>
Note that the proof of Theorem 36.2 is nonconstructive. For a given language <I>L</I> <img src="../images/memof12.gif"> P, we may not actually know a bound on the running time for the algorithm <I>A</I> that accepts <I>L</I>. Nevertheless, we know that such a bound exists, and therefore, that an algorithm <I>A</I>' exists that can check the bound, even though we may not be able to find the algorithm <I>A</I>' easily.<P>
<P>







<h2><a name="09ff_1c9e">Exercises<a name="09ff_1c9e"></h2><P>
<a name="09ff_1c9f">36.1-1<a name="09ff_1c9f"><P>
<a name="09ff_1c99"><a name="09ff_1c9a">Define the optimization problem LONGEST-PATH-LENGTH as the relation that associates each instance of a undirected graph and two vertices with the length of the longest simple path between the two vertices. Define the decision problem LONGEST-PATH = {<img src="../images/lftwdchv.gif"><I>G, u, v, k</I><img src="../images/wdrtchv.gif"><I> </I>: <I>G</I> = (<I>V, E</I>) is an undirected graph, <I>u, v</I> <img src="../images/memof12.gif"> <I>V</I>, <I>k</I> <img src="../images/gteq.gif"> 0 is an integer, and there exists a simple path from <I>u</I> to <I>v</I> in <I>G</I> whose length is at least <I>k</I>}. Show that the optimization problem LONGEST-PATH-LENGTH can be solved in polynomial time if and only if LONGEST-PATH <img src="../images/memof12.gif"> P.<P>
<a name="09ff_1ca0">36.1-2<a name="09ff_1ca0"><P>
<a name="09ff_1c9b">Give a formal definition for the problem of finding the longest simple cycle in an undirected graph. Give a related decision problem. Give the language corresponding to the decision problem.<P>
<a name="09ff_1ca1">36.1-3<a name="09ff_1ca1"><P>
Give a formal encoding of directed graphs as binary strings using an adjacency-matrix representation. Do the same using an adjacency-list representation. Argue that the two representations are polynomially related.<P>
<a name="09ff_1ca2">36.1-4<a name="09ff_1ca2"><P>
<a name="09ff_1c9c"><a name="09ff_1c9d">Is the dynamic-programming algorithm for the 0-1 knapsack problem that is asked for in Exercise 17.2-2 a polynomial-time algorithm? Explain your answer.<P>
<a name="09ff_1ca3">36.1-5<a name="09ff_1ca3"><P>
Suppose that a language <I>L</I> can accept any string <I>x </I><img src="../images/memof12.gif"><I> L </I>in polynomial time, but that the algorithm that does this runs in superpolynomial time if <I>x </I><img src="../images/notmem.gif"><I> L. </I>Argue that<I> L</I> can be decided in polynomial time.<P>
<a name="09ff_1ca4">36.1-6<a name="09ff_1ca4"><P>
Show that an algorithm that makes at most a constant number of calls to polynomial-time subroutines runs in polynomial time, but that a polynomial number of calls to polynomial-time subroutines may result in an exponential-time algorithm. <P>
<a name="09ff_1ca5">36.1-7<a name="09ff_1ca5"><P>
Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if <I>L</I><SUB>l</SUB>, <I>L</I><SUB>2</SUB> <img src="../images/memof12.gif"> P, then <I>L</I><SUB>l</SUB> <img src="../images/wideu.gif"> <I>L</I><SUB>2</SUB> <img src="../images/memof12.gif"> P, etc.<P>
<P>


<P>