Some thoughts about NP Problems

Due to the book "Nature of Computation", consider a problem A, if there exists a witness w such that (x, w) is a yes-instance of B, where B is a decision problem in P regarding pairs (x, w), and x is a yes-instance of A, and where |w| = poly(|x|), then this problem A can be classified as a member of the set NP.

So consider the Minimum Spanning Tree (aka. MST) problem, given a spanning tree T, and we are requested to check whether it is the solution for the graph G. Though T can be regarded as the witness w and |w| = poly(|V| + |E|). However, because we don't know the sum of weights of the MST of G in advance, then we have two methods to check this instance.

The first one is to use either Prim's or Kruskal's Algorithm to generate a MST of G and compare its sum of weights with that of T. If they are equal, then this instance is a yes-instance.

The second method may seem a little bit more complicated. We can take advantage of Lemma 3.1. Namely, during each iteration we choose one edge of T and add it in the set T' which is initially empty. Then we check the edges connecting T'.V and (G - T').V. If this edge is the lightest one among those across these two subsets, then we continue this iteration. If not, we just terminate the algorithm and say that T is not a yes-instance. If all the edges in T are checked and there's no termination, we can end the algorithm and say that T is a yes-instance of this problem.

Comparing the above two methods, I'll buy the first one. 

Thoughts about Machine Learning

In the book "All of Statistics", the author believed that Machine Learning should be called Statistical Inference in order to reveal its core thoughts. However, I've found that Machine Learning should be much more than that. It contains many thoughts in Neural Science and Clustering, besides Bayesian Inference and Hypothesis Test.

Nowadays, Machine Learning is becoming more and more popular, -- not only among scientists of Computer Science and Statistics, but almost everyone in the fields of Natural and Social Science. I don't know whether scholars in Art, Humanities or History are interested in Machine Learning. But I hope not.

I don't whether it is a good news that it becomes so popular. More and more smart persons are working on it, but I see no theoretical breakthrough hitherto. And I don't want to join this revelry.

I know that statistics can be used as a concrete tool to resolve many real-world problems perfectly. I will learn it well. But I don't believe that it can be the Messiah for science, especially for Artificial Intelligence.

My purpose of studying science is to know deeply about western philosophy. I like the feeling that I can help promote the world, but I don't want to be an engineer. I want to be a teacher -- not a teacher in high school or primary school, but a teacher of both Oriental and Western cultures and philosophies.

Thus, I cannot be crazy about Machine Learning. I will step towards the kernel of Artificial Intelligence without any stop. For ML, I regard it as a concrete tool, but not a comprehensive theory which can help me reach the philosophy hiding behind it.

More about GEB

GEB is really a fantastic book. And I believe that the movie "Inception" should have borrowed many concepts and inspirations from it.

For instance, in the movie, they just pushed themselves into recursively constructed dreams in order to do the inception. Then in the book, tortoise and Achilles went into recursively constructed drawings by Escher. In the movie, they used ticks to pop out of the deeper dreams. And in the book, they used tonic or popcorns to jump into the higher level.

But what's more, the book contains some interesting concepts that the movie didn't mention. One is the corrupt of the system. When a Genie asked Achilles to say his three wishes. Achilles just say one wish: "I wish my wish would not be granted!" How clever! It is a paradox, which resulted in the corrupt of the system. And after the system recovered, they were standing in another drawing, with lizards and their tonic remaining. So the author explained the concept of recovery of recursion in a fairly clever way!

Once started reading, can't I stop. What a brilliant book!

My Dreams

Prof. Luger asked me to think about my goal, which is what I really want to be after 20 years. Then I took time to seriously think of this question, and the following are my answers:

First of all, I love Computer Science. I believe that it's a powerful tool to promote the world and change people's way of living. Moreover, I know that mathematics is the foundation of western philosophy. If I want to step into this area, I should be familiar with mathematics. Then Computer Science is a wonderful way to achieving this. During my undergraduate life, I started to love mathematics because of Discrete Mathematics. I've changed my attitude towards mathematics due to Computer Science. So, I will continue this process along with Computer Science.

Then, I wish that someday in the future, I can be free to teach Confucianism in China. Hitherto, Chinese government does not allow citizens to hold any school. And after the damage over one century, Confucianism has become strange to most of Chinese people. Two years ago, I became a believer of Confucianism. Since then, besides my study, I started to read and recite ancient scripts of Confucianism. As I'm more familiar with Confucianism, I feel that more and more Chinese should know about it. It's the accumulation of the intelligence of ancient Chinese culture, and it does have the inspiration for China to restore its ideology and culture and become a modern and simultaneously exotic country.

Comparing these two dreams, since it's impractical  to do the latter one now, I will continue my first dream definitely. But besides, I will keep on learning Confucianism, so as to make myself prepared for the future teaching. I believe that this day will come soon or later.

Recent Reading

Introduced by the Swarm Agent AI club, I have started to read the book "Gödel, Escher, Bach: an Eternal Golden Braid" since the week before last. Hitherto, my step reaches Chapter 3.

From the previous chapters, I found that the author endeavored to combine the related concepts of music, drawing and mathematics as a sole theme to make readers interested in the topic of Artificial Intelligence. From Chapter 1 to 3, he referred to the formal system to carry the abstract concepts of isomorphism, theorem, recursion, etc.. And the drawings of Escher and the conversations between Achilles and Tortoise can be a beautiful metaphor for his explanation. 


What's more, each chapter just conveys one core concept, which makes me comfortable and never feel overloaded. Such an arrangement of the book can lead me to be addicted in the thought and questions of the author. What a great strategy!

 

Waterfall by Escher, describing a "Strange Loop"

Life seems Overwhelming

Right after the fall break, there came two Midterm exams, one programming homework and one mathematics homework. What's more, I find myself fall behind the process of Neural Networks course. And for Algorithm course, it's still difficult for me to catch up with others. The only one that I'm confident with is CS 530. However, the professor is talking about Fourier Transformation, which is somehow the most difficult part of this course.

Life seems overwhelming now. Besides the course work, I keep on reading GEB and the AI book that Prof. Luger gave to me. I really want to be stronger in AI field, and don't want the professor to be disappointed with me. So I have no other choice but to keep on fighting.

Maybe this afternoon's Loopy Group Meeting will be canceled from my schedule. I feel really tired after spending almost the whole night twice. I need courage and break, and then come back to the lasting war.

Time doesn't wait for anyone

It's a month since I entered the USA. Hitherto, everything seems going well. However, I feel a little lazy during recent days. I know it's crime to behavior like this, so I write this article to warn myself.


What's more, I'm sure that I have wrongly looked down upon my American classmates. Though they think about problems in a different way than mine, they are still clever and they courage to communicate with professors in class. I'm lack of such a courage, and my mathematical skill still remains weak.

So it's the time to stand up, and continue to fight for my dream. Time doesn't wait for anyone.