tag:blogger.com,1999:blog-76845443943392983532024-03-04T20:37:17.176-08:00Andrew's ComplexityAndrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-7684544394339298353.post-26171506074450827622017-12-08T21:08:00.000-08:002017-12-08T21:08:01.983-08:00NP Completeness (4) - EXACT-4-SET<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: left;">
<b>Problem:</b></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgUJdd2S9vhvbmzaHH0Y0d8wAspHIdkqzANPpZF9WzxkSOxfUTnUyq8wbDu7oiIWlEzlD9dLqvG2GN_QmG_6iYkqKsfaif1I5oni8nm9TbejSdCRJbKHL7WTbmSfQCw5QMyWWjeQVtQVTVz/s1600/EXACT-4-SAT.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="135" data-original-width="1600" height="54" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgUJdd2S9vhvbmzaHH0Y0d8wAspHIdkqzANPpZF9WzxkSOxfUTnUyq8wbDu7oiIWlEzlD9dLqvG2GN_QmG_6iYkqKsfaif1I5oni8nm9TbejSdCRJbKHL7WTbmSfQCw5QMyWWjeQVtQVTVz/s640/EXACT-4-SAT.PNG" width="640" /></a></div>
<br />
<b>Solution:</b><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiLURdeB9Eqpjw0u1-b2dAuJvl0yeaPFH852nApJ1Hbh7RBLkLXHozcZMapmqRuruiymPLRwIrSpfs3BGb3QJ2IQjvUOLEYL6c2GE_kKUuCIGwJt2rs91W3LihsiW9841dlzcY-5ros-X_8/s1600/Solution1.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="834" data-original-width="728" height="640" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiLURdeB9Eqpjw0u1-b2dAuJvl0yeaPFH852nApJ1Hbh7RBLkLXHozcZMapmqRuruiymPLRwIrSpfs3BGb3QJ2IQjvUOLEYL6c2GE_kKUuCIGwJt2rs91W3LihsiW9841dlzcY-5ros-X_8/s640/Solution1.PNG" width="558" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwEicDSu2yw6pwWP2OEH7AvsVPORUv3fi4FO8fc2Cxjh-ijr40wN0Jh1K8a2N7txXiznw4NRU-ZoUk4DBnIGcLFA29jYc3TeY-22tCMErBqW77YmX8A1A06ImuyfUmsUojc-FgJNHwHyHZ/s1600/Solution2.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="552" data-original-width="720" height="490" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwEicDSu2yw6pwWP2OEH7AvsVPORUv3fi4FO8fc2Cxjh-ijr40wN0Jh1K8a2N7txXiznw4NRU-ZoUk4DBnIGcLFA29jYc3TeY-22tCMErBqW77YmX8A1A06ImuyfUmsUojc-FgJNHwHyHZ/s640/Solution2.PNG" width="640" /></a></div>
<br /></div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-71809557034705081762017-03-20T13:34:00.003-07:002017-03-20T13:34:56.469-07:00NP completeness (3) - Show that Set Cover is NP complete<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem 1 - Prove that Set Cover is in NP.</b><br />
<br />
We will use the set ids as a certificate. The number of set ids is at most $ n $ and therefore the size of the certificate is $ O(n) $ and is polynomial in the size of the problem.<br />
<br />
To verify the solution, we can check that there are $ k $ set ids, and their union is the universal set. Checking there are $ k $ set ids take $ O(1) $ time, and checking if the union covers the set take at most $ O(k) \times O(|P|) $ time, where $ |P| $ is the problem size, therefore, we can check if a certificate is valid in polynomial time.<br />
<br />
Therefore k-SET Cover is in NP.<br />
<br />
<b>Problem 2 - Show that Set-Cover in NP complete</b><br />
<b><br /></b>
In problem 1 - we have already shown Set-Cover is in NP, so all we have to do is to reduce Vertex Cover to Set Cover. The key idea is that we map an edge to be an element in the set cover problem, and a node into a set of edges that it connects to. Now, the problem of choosing a subset of node to cover all edges becomes choosing the set of edges corresponding to the node to cover the edges, the latter is obviously a set cover problem.<br />
<br />
Suppose there exists a set-cover of $ k $ sets, we know each of these $ k $ set corresponding to exactly one node. We claim that the nodes corresponding to the set is indeed a vertex cover. We know that the $ k $ set cover all edges, in particular, for any edge $ e $, there exists at least one set $ x $ cover it. The node $ n $ corresponding to $ x $ must have $ e $ connected to it, so $ e $ is covered. Because that must be true for all edges, we conclude when the set cover problem found a set cover, we also find a vertex cover.<br />
<br />
Suppose there does not exist a set-cover of $ k $ sets, and suppose there does exist a vertex-cover of $ k $ vertices, we will derive a contradiction. That will conclude our proof because we show that if set-cover reports there is no set-cover, there is no vertex cover. Consider the sets associated with the $ k $ vertices, this must include all edges because it is a vertex cover, therefore, there does exist a $ k $ set-cover, so we reached the desired contradiction.<br />
<br />
Last but not least, the mapping from a node to a set can spend at most $ |p|^2 $ time (in the worst case of a complete graph), therefore the reduction takes polynomial time.<br />
<br />
To summarize, we have shown:<br />
<br />
<ul style="text-align: left;">
<li>Set cover is in NP - in problem 1</li>
<li>A vertex cover problem instance can transform into a to set cover problem instance in polynomial time - the last part above</li>
<li>The transformation preserve yes instances - the first proof</li>
<li>The transformation preserve no instances - the second proof</li>
</ul>
<br />
Therefore we gladly conclude set-cover in NP complete!</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-67413489502171352112017-03-08T14:58:00.000-08:002017-03-08T14:58:34.792-08:00NP completeness (2) - Show that k-Clique is NP complete<div dir="ltr" style="text-align: left;" trbidi="on">
It is easy to show k-Clique is in NP, given a k-clique, we can use it as the certificate. The size of the certificate is at most the number of nodes, which is polynomial of the input size. We need to verify that it is indeed a k-clique, which can be simply checked by testing all pairs are edges, which take times $ O(E) $ and is certainly polynomial in time in the input size.<br />
<br />
To prove that it is NP complete, we reduce the independent set problem to it.<br />
<br />
Suppose we need to solve the problem that whether or not a graph of $ |V| $ node contains an independent set of $ k $ nodes, we can solve the problem by asking whether or not the complement of the graph has a clique of $ k $ nodes. Note that the complement $ \bar{G} $of a graph $ G $ is defined by having the same vertex set, $ u $ and $ v $ are connected as an edge in $ \bar{G} $ if and only if they are not an edge in $ G $<br />
<br />
Suppose there exists a clique of $ k $ nodes in $ \bar{G} $, we conclude that the same set of nodes is an independent set of $ G $. This is obvious because those nodes are all directly connected in $ \bar{G} $, and therefore not connected to each other in $ G $.<br />
<br />
Suppose there does not exists a clique of $ k $ node in $ \bar{G} $, we conclude that there does not exists an independent set of $ k $ nodes, for if it does, it would have been the $ k $ clique in $ \bar{G} $.<br />
<br />
With that, we can reduce the independent set problem to $ k $ clique, therefore $ k $ clique is NP complete.<br />
<div>
<br /></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-44576266293660598422017-03-08T14:56:00.000-08:002017-03-08T14:56:01.348-08:00NP completeness (1) - Vertex Cover<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Prove that Vertex Cover is NP complete.<br />
<br />
<b>Solution:</b><br />
<br />
We will assume the independent set problem is NP complete.<br />
<br />
It is easy to show Vertex Cover is in NP, given a vertex cover, we can use it as the certificate. The size of the certificate is at most the number of nodes, which is polynomial of the input size. Given the certificate, we can simply iterate through the set of all edges and check that the given node indeed cover all edges, such an algorithm that $ O(E) $ time and is certainly polynomial in time in the input size.<br />
<br />
To prove that it is NP complete, we reduce the independent set problem to it.<br />
<br />
Suppose we need to solve the problem that whether or not a graph of $ |V| $ node contains an independent set of $ k $ nodes, we can solve the problem by asking whether or not we have a vertex cover of $ |V| - k $ nodes.<br />
<br />
Suppose there exists a vertex cover of $ |V| - k $ nodes, we claim the complement of the vertex cover is an independent set. Indeed, if the complement is not an independent set, then there exists an edge such that both end points is in the complement, that means both end points were not in the vertex cover, of course that is impossible because a vertex cover must cover all edges.<br />
<br />
Suppose there does not exist a vertex cover of $ |V| - k $ nodes, then we claim that there does not exist an independent set of $ k $ node. If there does exist an independent set of $ k $ nodes, we claim that the complement of the independent set is a vertex cover. Indeed, if the complement is not a vertex cover, then there must exists an edge that is does not cover, but that would mean both ends on that edge is included in the independent set, which is clearly impossible.<br />
<br />
With that, we conclude that we can reduce independent set, a known NP complete problem, to vertex cover, therefore, vertex cover is NP complete too.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-73641539273048840392017-02-27T08:24:00.001-08:002017-02-27T08:24:41.762-08:00Recursion Theorem in Practice - building a quine in C#<div dir="ltr" style="text-align: left;" trbidi="on">
The goal of this post is to share my experience building a C# program that output its own source. This is often known as a quine.<br />
<br />
According to the recursion theorem, a Turing machine can reference its own representation. So a quine, if built, serve as an example to show recursion theorem is true in this case.<br />
<br />
Without further ado, here is the C# program I built. It can generate it an identical copy of its own source code to the console.<br />
<br />
<span style="color: red; font-family: Courier New, Courier, monospace;">class Program</span><br />
<span style="color: red; font-family: Courier New, Courier, monospace;">{</span><br />
<span style="color: red; font-family: Courier New, Courier, monospace;"> static void Main()</span><br />
<span style="color: red; font-family: Courier New, Courier, monospace;"> {</span><br />
<span style="color: red; font-family: Courier New, Courier, monospace;"> string tape = <span style="background-color: orange;">@" string a = @""class Program</span></span><br />
<span style="background-color: orange; color: red; font-family: Courier New, Courier, monospace;">{</span><br />
<span style="background-color: orange; color: red; font-family: Courier New, Courier, monospace;"> static void Main()</span><br />
<span style="background-color: orange; color: red; font-family: Courier New, Courier, monospace;"> {</span><br />
<span style="background-color: orange; color: red; font-family: Courier New, Courier, monospace;"> string tape = @"""""" + tape.Replace(""\"""", ""\""\"""") + @"""""";</span><br />
<span style="background-color: orange; color: red; font-family: Courier New, Courier, monospace;">"";</span><br />
<span style="background-color: orange; color: red; font-family: Courier New, Courier, monospace;"> System.Console.WriteLine(a + tape);</span><br />
<span style="background-color: orange; color: red; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: red; font-family: Courier New, Courier, monospace;"><span style="background-color: orange;">}"</span>;</span><br />
<span style="color: blue; font-family: Courier New, Courier, monospace;"> string a = <span style="background-color: cyan;">@"class Program</span></span><br />
<span style="background-color: cyan; color: blue; font-family: Courier New, Courier, monospace;">{</span><br />
<span style="background-color: cyan; color: blue; font-family: Courier New, Courier, monospace;"> static void Main()</span><br />
<span style="background-color: cyan; color: blue; font-family: Courier New, Courier, monospace;"> {</span><br />
<span style="color: blue; font-family: Courier New, Courier, monospace;"><span style="background-color: cyan;"> string tape = @"""</span> + tape.Replace("\"", "\"\"") + <span style="background-color: cyan;">@""";</span></span><br />
<span style="color: blue; font-family: Courier New, Courier, monospace;"><span style="background-color: cyan;">"</span>;</span><br />
<span style="color: blue; font-family: Courier New, Courier, monospace;"> System.Console.WriteLine(a + tape);</span><br />
<span style="color: blue; font-family: Courier New, Courier, monospace;"> }</span><br />
<span style="color: blue; font-family: Courier New, Courier, monospace;">}</span><br />
<span style="font-family: inherit;"><br /></span>
The coloring is intended to show how this quine is constructed. The red part of the program is intended to construct the blue part of the program. In fact, the whole highlighted part in the red program is really just a string literal that is the same as the blue part. Therefore the definition of the red part depends on the blue part.<br />
<br />
Now the blue part must construct the red part and concatenate them together. But we have a small problem here. The blue part's definition cannot depend on the red part's, otherwise we have a dependency cycle. The key is that we compute the red part instead. That is why we used three strings to compute a variable named a, and once we get the red part, we get the blue part from the tape variable, and therefore we completed constructing the whole source code, now we output it!<br />
<br />
Try to run the program and use a diff tool to compare the source code, they are identical! Not a space is missing!</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-89509521043678880502017-01-04T07:45:00.002-08:002017-01-04T07:45:11.836-08:00Languages<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<b><br /></b>
Mixing it up: Let $ F $ denote some finite language, $ R $ denote some regular language, $ C $ denote some context-free language, $ D $ denote some decidable language, $ E $ denote some<br />
recognizable language, and $ N $ denote some non-recognizable language. For each one of the<br />
following statements, prove whether it always holds, sometimes holds, or never holds:<br />
<br />
<br />
<b>$ N - D $ is recognizable</b><br />
<br />
Short answer: never<br />
<br />
Support I could enumerate $ N - D $, I can also enumerate $ D $ because $ D $ is decidable. Now I can dovetail to enumerate $ N = (N - D) \cup D $, therefore I should not be able to enumerate $ N - D $.<br />
<br />
<b>$ RE $ is context free </b><br />
<br />
Short answer: sometimes<br />
<br />
A finite language is recursive enumerable and also context free.<br />
A recursively enumerable language include $ a^n b^n c^n $, which is not context free.<br />
<br />
<b>$ N \cap F $ is decidable</b><br />
<br />
Short answer: always<br />
<br />
$ N \cap F $ is finite, and a finite language is always decidable.<br />
<br />
<b>$ E \cup F $ is recognizable</b><br />
<br />
Short answer: sometimes<br />
<br />
E is a recognizable language, it could be finite. F is finite, so E union F could be finite, and a finite language is regular.<br />
<br />
E could be $ a^n b^n $, and $ F $ could be the empty language, so $ E \cup F $ is $ a^n b^n $ and is not regular.<br />
<br />
<b>$ N^* $ is non recognizable</b><br />
<br />
Short answer: always<br />
<br />
If $ N* $ is recognizable, we will have a Turing machine that halt on $ N* $. We can modify that machine such that whenever it reach a final state, any input will go to a state that just consume the input and do nothing and never halt, that would become a recognizer for $ N $.<br />
Therefore $ N^* $ is not recognizable.<br />
<br />
<b>$ N \cup C $ is finite</b><br />
<br />
Short answer: never<br />
<br />
If $ N \cup C $ is finite, then $ N $ is finite, but finite language is always recognizable.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-12062092300225656322017-01-04T07:39:00.001-08:002017-01-10T07:32:44.246-08:00Coloring Cyborgs<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Two cyborgs walk into your home, both claiming to be oracles for the graph 3-colorability decision problem. They both always give a yes/no answer in constant time for any instance, and are each self-consistent (i.e. each always gives the same answer for the same instance). However, one is a true oracle and the other is a shameless impostor, and you have a large instance of 3-colorability upon which they disagree. Prove whether it is possible to expose the impostor within time polynomial in the size of that instance.<br />
<br />
<b>Short Answer:</b><br />
<br />
The key idea is to use the oracle (that only tell me yes or no) to output the coloring. The one that gives a valid coloring is the right one.<br />
<br />
<b>Proof:</b><br />
<br />
We need a gadget for that, first, we add three nodes (call them red - green - blue ) as a triangle to the graph. If we wanted to force a node to be red, simply connect green and blue to it.<br />
<br />
Now we have a mechanism to force a node to have a certain color - now we can guess the color of the nodes. Here is an algorithm to extract the 3 coloring from it.<br />
<br />
For the cyborg that said the graph is 3 colourable, we run this algorithm:<br />
<br />
while (there exists uncolored node)<br />
{<br />
color it red<br />
if (the colored graph is not 3 colourable)<br />
{<br />
color it green instead<br />
if (the colored graph is not 3 colourable)<br />
{<br />
color it blue instead<br />
if (the coloured graph is not colourable)<br />
{<br />
output "you are fake oracle!";<br />
}<br />
}<br />
}<br />
}<br />
output you are true oracle!<br />
<br />
The algorithm do at most 3 coloring attempt for each node, so it is obviously polynomial time!<br />
<div>
<br /></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-9184816406030014852017-01-04T07:36:00.001-08:002017-01-04T07:36:27.108-08:00A Turing-recognizable language consisting of descriptions of Turing machines<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Let $ A $ be a Turing-recognizable language consisting of descriptions of Turing machines, $ \{(M_1 ), (M_2), \cdots \}$, where every $ M_i $ is a decider. Prove that some decidable language $ D $ is not decided by any decider $ M_i $ whose description appears in $ A $.<br />
(Hint: You may find it helpful to consider an enumerator for $ A $.)<br />
<br />
<b>Short answer: </b><br />
<br />
We can adopt the diagonalization argument to produce a decidable language that is not accepted by any of the $ M_i $.<br />
<br />
<b>Proof:</b><br />
<br />
Consider the language $ D $ decided by the following Turing machine<br />
<br />
Reject any input that is not a binary number.<br />
Enumerate the ith Turing machine, where $ i $ is the input string.<br />
If $ M_i $ accept the input string, reject it, otherwise accept it.<br />
<br />
Apparently this is a Turing machine, and it is not accepted by any of the $ M_i $ (there is always a string $ i $ where $ M_i $ does not agree with $ D $)<br />
<br /></div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-43498506379380243772017-01-04T07:32:00.000-08:002017-01-04T07:32:05.782-08:00Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.<br />
<br />
<b>Proof idea:</b><br />
<br />
The number of Boolean function is huge (i.e. exponential exponential) but the number of circuit you can make out of polynomial number of gates is smaller than that.<br />
<br />
<b>Proof:</b><br />
<br />
The number of Boolean functions of n input can be counted by listing the output of the Boolean function output starting from<br />
<br />
00000..000 = 0<br />
00000..001 = 0<br />
...<br />
<br />
There are $ 2^n $ rows, therefore every unique bit string of length $ 2^n $ represents an unique Boolean function, so we have $ 2^{2^n} $ Boolean functions.<br />
<br />
On the other hand, if we have a polynomial number of gates, they could be arranged in anyway, the number of circuits could be at most $ (cn^s)! < 2^{cn^s} < 2^{2^n} $, therefore, most of the circuits do require more than polynomial number of gates.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-76576926683056353302017-01-04T07:29:00.003-08:002017-01-04T07:29:47.316-08:00Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.<br />
<br />
<b>Short proof: </b><br />
<br />
If such an infinite subset exists, we can compress those strings using a Turing enumerator.<br />
<br />
<b>Proof:</b><br />
<br />
If such an infinite subset exists, we build an enumerator of them. By the recursion theorem, we can build a Turing machine that enumerate the strings that infinite subset and stop on the first string that is larger than the representation of itself.<br />
<br />
Such a machine must eventually halt because of the set must have a string with length larger than this finite machine.<br />
<div>
<br /></div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-84550551287190609682017-01-04T07:28:00.000-08:002017-01-04T07:28:06.292-08:00Show that NP is closed under union and concatenation<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem:</b><br />
<br />
Show that NP is closed under union and concatenation<br />
<br />
<b>Short answer: </b><br />
<br />
We can build non-deterministic Turing machine to solve the union language and the concatenation language<br />
<b><br /></b>
<b>Proof:</b><br />
<br />
<i>Assume language X and language Y are in NP, we wanted to show X union Y is in NP</i><br />
<br />
Because X and Y are in NP, there exists non-deterministic Turing machine X and non-deterministic Turing machine Y that verifies X and Y, respectively.<br />
<br />
Rename the states in Y so that it does not have the same name as in X.<br />
<br />
Build a new non-deterministic Turing machine U as follow:<br />
<br />
Create a new start state, for each input symbol, it write the same symbol back to the tape, and non-deterministically go to the start state of X or the start state of Y. Take the union of state and transition function from both X and Y, that is a non-deterministic Turing machine U.<br />
<br />
For any string in X, non-deterministic Turing machine U can take a non-deterministic jump to the start state of X, and follow the non-deterministic Turing machine X to finally get accepted.<br />
For any string in Y, non-deterministic Turing machine U can take a non-deterministic jump to the start state of Y, and follow the non-deterministic Turing machine Y to finally get accepted.<br />
For any string that is neither in X nor in Y, non-deterministic jump to either X or Y cannot lead to acceptance.<br />
<br />
Therefore we showed the non-deterministic Turing machine U precisely accept X union Y.<br />
<br />
<i>Assume language X and language Y are in NP, we wanted to show X concatenate Y is in NP</i><br />
<br />
Because X and Y are in NP, there exists non-deterministic Turing machine X and non-deterministic Turing machine Y that verifies X and Y, respectively.<br />
<br />
Rename the states in Y so that it does not have the same name as in X.<br />
<br />
Build a new non-deterministic Turing machine C as follow:<br />
<br />
For each final state in X, for each input symbol, write the same symbol back to the tape and jump to the start state of Y, and make it non-final.<br />
<br />
For any string in X concatenate Y, it can follow the non-deterministic Turing machine X to go to final state of the original non-deterministic Turing machine X, jump to start state of Y, and then follow it to the final state of Y.<br />
<br />
For any string, it cannot possibly go to a final state without going through a original final state of X. (All path to final state goes through it)<br />
<br />
But if it goes through to final state through a original final state of X, the string could be split into two pieces where a prefix is in X and a suffix is in Y, that means the string has to be in X concatenate Y.<br />
The contrapositive of this show if a string is not in X concatenate Y, it is not accepted.<br />
<br />
Therefore we showed the non-deterministic Turing machine C precisely accept X concatenate Y.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-54169500905573617762017-01-04T07:24:00.001-08:002017-01-04T07:24:14.903-08:00Is NP countable?<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem: </b><br />
<br />
Is NP countable?<br />
<br />
<b>Short answer: </b><br />
<br />
yes<br />
<br />
<b>Proof:</b><br />
<br />
For each problem in NP - there exists a non-deterministic Turing machine as verifier.<br />
As we can encode non-deterministic Turing machine as finite binary string, the set of non-deterministic Turing machine is countable, therefore the set NP is also countable.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-19072876865939729752014-10-16T14:09:00.003-07:002014-10-16T14:09:58.166-07:00Problem 1.32<div dir="ltr" style="text-align: left;" trbidi="on">
The key to this problem is to construct a DFA that can recognize that reverse sum language. With that, we can invoke problem 1.31 to show the sum language is also regular.<br />
<br />
The proposed DFA has 3 states, the first state is the start state and represents the last digit has no carry, and the second state is the with carry state represents the last digit has a carry. The third state is the error state. The first state is also the final state.<br />
<br />
To simplify discussion, any unrecognized alphabet in a state go to the error state, and it stuck forever there by having all alphabets points towards it.<br />
<br />
Now in the start state, we have these transitions:<br />
<br />
$ \left(\begin{matrix} 0 \\ 0 \\ 0\end{matrix}\right) $ , $ \left(\begin{matrix} 0 \\ 1 \\ 1\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 1\end{matrix}\right) $ goes to start state.<br />
$ \left(\begin{matrix} 1 \\ 1 \\ 0\end{matrix}\right) $ goes to carry state.<br />
<br />
In the carry state, we have these transitions:<br />
<br />
$ \left(\begin{matrix} 0 \\ 0 \\ 1\end{matrix}\right) $ goes to the start state<br />
$ \left(\begin{matrix} 0 \\ 1 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 0 \\ 0\end{matrix}\right) $ and $ \left(\begin{matrix} 1 \\ 1 \\ 1\end{matrix}\right) $ does to carry state.<br />
<div>
<br /></div>
<div>
That's it, we completed the description for the DFA that can recognize the reverse sum language. </div>
<div>
That shows the reverse sum language is regular. By problem 1.31, the sum language is also regular!<br />
<br />
Q.E.D.</div>
</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-19862598451681795972014-10-10T08:12:00.003-07:002014-10-10T08:12:10.455-07:00Problem 1.31<div dir="ltr" style="text-align: left;" trbidi="on">
Finally, we really doing something about the theory of computation!<br />
<br />
To show the reverse $ L^R$ of a regular language L is also regular. We will construct a non-deterministic finite automata (NFA) for the language. Since L is a regular language, it has a deterministic finite automata (DFA).<br />
<br />
The idea is simply to run the DFA backward. But there is one complication - a DFA could have multiple final states. So we simply extend the original DFA to NFA by joining merging all the final states to a single final state with epsilon transition.<br />
<br />
Then we reverse all transitions to go backward, using the merged final state as start state, and the original start state as the final state, we obtain a NFA for the reverse language.<br />
<br />
To show the constructed NFA actually works. Consider a string w in L, there exist a path from the original start state to the merged end state. So there exist a reverse path in the constructed NFA as well. The transitions are exactly the same as it was, only in reversed order, so the reverse string is recognized.<br />
<br />
For a string that is NOT in w, however, the original DFA will lead to a non-final state, so we cannot take the epsilon path to the merged final state. Note that before exhausting all input symbols, it might reach the final state and took the epsilon path before. But since the merged final state does not consume any symbol, the path cannot extend there.<br />
<br />
Now assume somehow the reverse is accepted, so there exists a path from the merged final state back to the original start state with symbols reversed, but then it would mean a path exist from the original start state to the merged final state by reversing it, which we already proved doesn't exist. The contradiction shows the reverse cannot be accepted.<br />
<br />
Together we show our constructed NFA accepts precisely the reverse language. So the reverse language is regular.</div>
Andrew Auhttp://www.blogger.com/profile/17519031924478773558noreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-36838387484193713692014-10-09T15:02:00.001-07:002014-10-09T15:02:17.661-07:00Problem 0.14This isn't really a problem computational theory. But I will complete this anyway.<br />
<br />
Define x to be the monthly payment. r to be the monthly interest rate, T be the number of months.<br />
<br />
Total future value of these payment is<br />
<br />
$ \sum\limits_{i = 0}^{T-1}{x(1+r)^{i}} = x\frac{(1+r)^n - 1}{(1 + r - 1)} = x\frac{(1+r)^n - 1}{r} $<br />
<br />
But then it must equals to the future value of the loan, so we have<br />
<br />
$ x\frac{(1+r)^n - 1}{r} = p(1+r)^n $<br />
<br />
Plugging in the values it is easy to see the answer is $536.82.<br />
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-81715250622819573482014-10-09T09:00:00.003-07:002014-10-09T09:00:49.757-07:00(*) Problem 0.13Moving forward, I will use a star in the subject to indicate the problem is not easy.<br />
<br />
As a first attempt, I tried <a href="http://theoremoftheweek.wordpress.com/2010/05/02/theorem-25-erdoss-lower-bound-for-the-ramsey-numbers/">Erdo's lower bound for Ramsay number</a>. It doesn't work, since larger than the lower bound says nothing about its relative magnitude with the actual Ramsay number.<br />
<br />
Now I try the hint on the book. <br />
<br />
Pick a node x.<br />
<br />
If x's degree is larger than a half of the number of remaining nodes. Then add it to pile A, and dump all the nodes that is not connected to x. Intuitively, we are trying to find a clique, so anything not connected to x is useless. We can dump at most half of the nodes.<br />
<br />
Otherwise x's degree is less than a half of the number of remaining nodes. Then add it to pile B, and dump all the nodes that is connected to x. Intuitively, we are trying to find an independent set, so anything connected to x is useless. Again, we can dump at most half of the nodes.<br />
<br />
The algorithm proceed until there is no more nodes. Any node in pile A must be connected to each other which means it is a clique. Any node in pile B must not connect to each other which mean it is an independent set.<br />
<br />
The algorithm can only throw at most half the number of nodes each time, which means it will take at least $ \log_{2}n $ steps to run. So in the worst case the nodes are distributed evenly so that the size of either clique or independent set is at least $\frac{1}{2}\log_{2}n$.<br />
<br />
Q.E.D.<br />
<br />
As as aside - this is a genius method - I couldn't have thought about it. I thought about trees (when I see logarithm, but I haven't thought about this simple algorithm)Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-3830534011613297822014-10-08T16:04:00.002-07:002014-10-08T16:06:44.775-07:00Problem 0.12 A graph can be decomposed into <a href="http://en.wikipedia.org/wiki/Connected_component_(graph_theory)">connected components</a>. Among the connected components, there exist one with maximum size. Suppose the connected component is K with |K| node. Assume K has more than 1 node, since K is connected, the degrees of the nodes in K must be at least 1 and at most |K|-1, but there are |K| nodes, by the <a href="http://en.wikipedia.org/wiki/Pigeonhole_principle">pigeonhole principle</a>, there must be two nodes with the same degree.<br />
<br />
On the other hand, if the maximum sized connected component has only 1 node, it must be the case that all nodes are not connected, pick any two nodes they will have the same degree = 0.<br />
<br />
<a href="http://q.e.d./">Q.E.D.</a><br />
<br />
<i>Aside 1: Graph theory is a great fun of it own - if I find good graph theory problem I will post it here.</i><br />
<i>Aside 2: It is a pleasure to type Q.E.D. I mean it!</i>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-21767815240478078022014-10-07T18:50:00.001-07:002014-10-07T18:50:05.376-07:00Problem 0.11This one is tricky. The simple observation is that this crap statement break down even when there are two horses, so let's expand the statement in that case.<br />
<br />
Assuming any set of one horse has the same color.<br />
<br />
Given a set H of two horses, name them by their color, let's say, black and white. The argument about H1 has only one color still follows. The argument that H2 has only one color still follow. But the last 'therefore' statement is flawed. It is possible for a set of horse to have two subset H1 and H2 of horses of the same color but H doesn't.<br />
<br />
This shows the induction breaks at the least breaking point, even if S(1), S(2) => S(3) => S(4) are all sound. As long as S(1) does not imply S(2), S(3), S(4) are just all as crap as all horse has the same color!Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-70579955948865730712014-10-07T18:17:00.002-07:002014-10-07T18:17:45.239-07:00Problem 0.10 This one is easy. The division by (a - b) is not a legal arithmetic operations since a = b, which implies (a - b) = 0. <br />
<br />
Heck, one can show anything equals to anything with this 'trick'. Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7684544394339298353.post-54564669507736215412014-10-07T18:03:00.003-07:002014-10-07T18:08:47.134-07:00Starting of the blogI am currently reading <a href="http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X">Introduction to the Theory of Computation</a> (<a href="http://www.icsd.aegean.gr/kaporisa/index_files/sipser.pdf">pdf</a>). The book is awesome in the sense that it takes away the boring detailed proof and replace them with ideas. It is also awesome with very interesting exercises.<br />
<br />
So I am writing this blog to document the answers to the problems I have attempted. Stay tuned.Unknownnoreply@blogger.com0