Complexity Theory

Tags:

Written by Min-Koo Seo

Chomsky’s hierarchy classifies language hierarchy based on characterics of stroage. For example, regular language can be accepted by dfa or nfa and these machines has 1 cell storage : state.

On the contrary, computational theory classfies language using time complexity. Most important concept which is requred when you deals with complexity is P and NP. P is union of DTIME(n^i) (i=0,1,…) and NP is union of NTIME(n^i) (i=0,1,2,…). P is more important and gives us more insight of problems vis-a-vis order of DTIME(n^i), i.e., i.

NP=P problem is in the center of language classification. To solve this problem, useful concept – NP-complete – is suggested. NP-complete is defined as follows :

Suppose L is a member NP. Then, every L’ which is a member of NP can be polinomial time reducible to L. We call L NP-complete.

One of such a NP-complete problems is satisfiability problem. If a specific conjuntion normal form can be true, then the cnf called satisfiable. Otherwise, called unsatisfiable.

For example, consider (x1 v x2) ^ (not x1) ^ (not x2). There is no x1 and x2 which can make the given cnf to true. So, this cnf is unsatisfiable. According to Cook’s theorem, satisfiability solution is NP-complete.

Another important concept in complexity theory is tractable. Tractable means the existence of practical solution. Even if there is DTIME(n^i) solution, say DTIME(n^100), such a algorithm can be quite impractical to use even a super computer is used. Cook-Karf thesis specify the term, tractable, as a P time solution. On the contrary, all non P time solution is called intractable.

However, this thesis does not perfect in some latitude. A good illustration of this is DTIME(n^100). Of course, this is in the range of P. Yet, it is quite inefficient. This implies that Cook-Karf thesis is based on empirical languages. As you know, almost all problems are within DTIME(n), DTIME(n^2), DTIME(n^3). Otherwise, problems tend to be solved in exponential time. Cook-Karf thesis concentrates on this fact, so the tractable is defined as described above.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *