Written by MinKoo Seo

It seems that NP is a universal set of all algorithm at first glance. Yet, there is a such problem that is not in NP.

One of the most famous problem is ‘Non-hamilton cycle problem.’ Hamilton cycle is a cycle which visits all vertices. Of course, no vertices can be repeated in this cycle by definition of the cycle.

One can easily think a solution of this problem : (1) find all cycles. (2) prove that those cycles is not hamilton cycle.

However, no one could not find non-deterministic polynomial time algorithm of this problem. So, it seems that this problem exists out of NP. In fact, according to my friend, Mr. Son, there is another complexity class beyond NP : co-NP class. (I do not want to delve into this problem. Therefore I did not check any references out.)

In the final analysis, a problem which is decidable is in co-NP.

———————-
August/22, 2003

I finally skim the book, ‘complexity theory’ to find NP-hard class. I could not find the definition of NP-hard, however.

What I met in this book is the definition of co-NP. co-NP is definied as L whose complement is NP. So, the conclusion of previous article is completely wrong.

There is other class which accepts nondeterministic exponential time complexity langauge.