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 "史蓋噗".


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:

Thank you for your advise.
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                      


Wednesday, July 20, 2005

Test for posting photos

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


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, 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