## Saturday, December 24, 2005

### Randomized algorithms and randomized life?

• 由隨機抽樣的一些點中取 average degree 與原圖的 average degree 差異和相關機率的關連？

• sublinear time algorithms 所花的時間事實上是否為 "expected running time"?

• 假設現在每次執行的 input 都不一樣（這假設是十分合理的），而 randomized algorithm 每次回答的答案也不盡相同，假設它能回答一個 expected answer，那麼對多個 inputs 多次執行這 randomized algorithm 的 expected answer 又是怎麼樣的一個值？

CCLin

## Sunday, December 04, 2005

### 創意工廠 MIT

MIT和Berkeley裡面的學生真厲害。希望我不要輸他們太多。

PS：今天三合一選舉結束了。願上帝祝福台灣 :)

Chuang-Chieh Lin

### 開始用中文記事好了

PS: 當然研究更重要，不然就沒意義了。 :P

Chuang-Chieh Lin

## Tuesday, September 27, 2005

### On L(2, 1)-labeling problem

Oh...It's really tiresome to modify other one's article.

My recent progress is rewriting senior W. H.'s master thesis. Half of the proofs were done.
I hope that I can finish this job as soon as possible.

Too tired I am now.

C. C. Lin in lab

## Monday, July 25, 2005

### Comparability graphs

Wow~~~Look at these definitions!!

Definition: (first)

A graph G = (V, E) is a comparability graph if there is a transitive orientation of its edges.

Definition: (second)
The comparability graph of a partial order (V,) has node set V, and edge (x, y) whenever xy or yx. G is a comparability if it is the comparability graph of some poset.

Definition: (third)
The comparability graph of a poset P = (X, ≦) is the graph with vertex set X for which vertices x and y are adjacent either xy or yx in P.

I'll keep studying the paper.

## Thursday, July 21, 2005

### How Do We Pronounce the Word "Skype"?

The answer is as follows.

Skype help

Skype rhymes with ripe and type.
In Chinese, we pronounce it by "史蓋噗".

Brilliant!!

### A nice blog

Wow. It's very cute.

I think all the paintings were done only by herself.

### If NP = P, then any problem not empty and not Σ* will be NP-complete

The answer was greatly supported by Prof. G. S. Huang.

------------------------------------------------------------------------------------------------

You are wrong.
Since in the assumption one supposes that P=NP, any problem in NP is also in P. Therefore you can solve any NP problem in polynomial time by a deterministic Turing machine under this assumption.

Your another point criticizes on how to find a "yes" instance and a "no" instance from A (which is the one that we intend to show NP-complete). This is indeed not a problem since such two instances always exists and do not bother one really to find them. Actually, you don't have to spend any time to find them since you only have to show that such a reduction does "EXIST" as long as such twoinstances exist.

----- Original Message -----
From: Chuang-Chieh Lin
To: Professor G. S. Huang
Sent: Thursday, July 14, 2005 3:23 PM
Subject: Re: Communication

Dear Professor Huang:

Recently I found some answers similar to yours.

However, I am still puzzled at how do we find "Y" and "N" in polynomial time.
Shouldn't we require a Turing machine doing this work?
It seems that finding a "Y" and finding an "N" would require exponential time
in the worst case although deciding whether an instance is an "Y" or "N" is of
polynomial time.

Sincerely yours,
Chuang-Chieh Lin

As for your problem, I think the reduction in Sipser's book
is the polynomial reduction. Suppose A is in P and B is in NP.
All you have to do is to prove that any B can be reduced to
such A in polynomial time.

There exist "yes" instances and "no" instances of A since A is not empty or full.
Let's call Y a "yes" instance and N a "no" instance. The reduction is as follows. For any instance of B, we do

1. Solve the instance in polynomial time. This becomes possible since we assume NP=P.
2. If the answer is yes, output Y; else output N.

This is indeed a polynomail-time reduction and you can show
that the instance is "yes" IF AND ONLY IF the output is a
"yes" instance of A, though this reduction is a little nonsense.
Therefore one can claim that A is NP-complete since A is in NP.

A letter coming from Professor G. S. Huang.
-----------------------------------------------------

### Test for emailing to my blog

Dear Turtle:

This is a test document.
That's all.

Best regards,
Chuang-Chieh Lin

---

Think hard, not work hard.
- Professor R. C. T. Lee

---

Chuang-Chieh Lin (林莊傑)
Dept. of Computer Science and Information Engineering,
National Chung-Cheng University
Homepage:
http://www.cs.ccu.edu.tw/~lincc
Email:
lincc@cs.ccu.edu.tw, s1321501@ncnu.edu.tw

---

## Wednesday, July 20, 2005

### Test for posting photos

Wow!! It is a shame for me to do such a stupid action.

Really.

### Chuan-Min Lee's new Blog was done!!

My senior, Chuan-Min Lee, built his blog.
Chuan-Min Lee's Blog: First post

His photo:

Welcome!! By the way, I have to go back to work now.

### My FIRST post here

My FIRST post!

Today I found http://www.blogger.com, then I registed to be a member of Bloggers.

Here I decided to post my feelings, thoughts, or ideas. This article is in memory of my first post at Bloggers.

I hope that I can graduate as soon as possible.

That's all.
C. C. Lin