theory of computation

P, NP, NP-Complete, NP-Hard

July 9, 2016 by arjun Leave a Comment

It might be because of the name but many graduate students find it difficult to understand $NP$ problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information)

$P$ Problems

As the name says these problems can be solved in polynomial time, i.e.; $O(n)$, $O(n^2)$ or $O(n^k)$, where $k$ is a constant.

$NP$ Problems

Some think $NP$ as Non-Polynomial. But actually it is Non-deterministic Polynomial time. i.e.; “yes/no” instances of these problems can be solved in polynomial time by a non-deterministic Turing machine and hence can take up to exponential time (some problems can be solved in sub-exponential but super polynomial time) by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if it is correct or wrong) in polynomial time by a deterministic Turing machine (or equivalently our computer). Examples include all P problems. One example of a problem not in $P$ but in $NP$ is Integer Factorization.

$NP$ Complete Problems$(NPC)$

Over the years many problems in $NP$ have been proved to be in $P$ (like Primality Testing). Still, there are many problems in $NP$ not proved to be in $P$. i.e.; the question still remains whether $P = NP$ (i.e.; whether all $NP$ problems are actually $P$ problems).

$NP$ Complete Problems helps in solving the above question. They are a subset of $NP$ problems with the property that all other $NP$ problems can be reduced to any of them in polynomial time. So, they are the hardest problems in $NP$, in terms of running time. If it can be showed that any $NPC$ Problem is in $P$, then all problems in $NP$ will be in $P$ (because of $NPC$ definition), and hence $P = NP = NPC$.

All $NPC$ problems are in $NP$ (again, due to $NPC$ definition). Examples of $NPC$ problems

$NP$ Hard Problems $(NPH)$

These problems need not have any bound on their running time. If any $NPC$ Problem is polynomial time reducible to a problem $X$, that problem $X$ belongs to $NP$ Hard class. Hence, all $NP$ Complete problems are also $NPH$. In other words if a $NPH$ problem is non-deterministic polynomial time solvable, it is a $NPC$ problem. Example of a $NP$ problem that is not $NPC$ is Halting Problem.

From the diagram, its clear that $NPC$ problems are the hardest problems in $NP$ while being the simplest ones in $NPH$. i.e.; $NP ∩ NPH = NPC$

Note

Given a general problem, we can say its in $NPC$, if and only if we can reduce it to some $NP$ problem (which shows it is in NP) and also some $NPC$ problem can be reduced to it (which shows all NP problems can be reduced to this problem).

Also, if a $NPH$ problem is in $NP$, then it is $NPC$

Some Reduction Inferences

25,432 total views, 2 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

P, NP, NPC, NPH

$P$ is a subset of $NP$, but whether $P = NP$ is still not known
$NPC$ is a subset of $NP$ (only if $P \neq NP$, $NPC$ is a proper subset of $NP$)
$NPC$ is a proper subset of $NPH$

Reduction

Reducing a problem $A$ to problem $B$ means converting an instance of problem $A$ to an instance of problem $B$. Then, if we know the solution of problem $B$, we can solve problem $A$ by using it.

Consider the following example:

You want to go from Bangalore to Delhi and you can get a ticket from Mumbai to Delhi. So, you ask your friend for a lift from Bangalore to Mumbai. So, the problem of going from Bangalore to Delhi got reduced to a problem of going from Mumbai to Delhi.

Some Inferences:

Consider problems $A$, $B$ and $C$.

Assume all reductions are done in polynomial time.

Two Important Points:

If $A$ is reduced to $B$ and $B$ $\in$ class $X$, then $A$ cannot be harder than $X$, because we can always do a reduction from $A$ to $B$ and solve $B$ instead of directly solving $A$. This reduction thus gives an upper bound for the complexity of $A$.
If $A$ is reduced to $B$ and $A$ $\in$ class $X$, then $B$ cannot be easier than $X$. The argument is exactly same as for the one above. This reduction is used to show if a problem belongs to $NPH$ – just reduce some known $NPH$ problem to the given problem. This reduction thus gives a lower bound for the complexity of $B$.

Somethings to take care of:

If $A$ is reduced to $B$ and $B$ $\in$ $NPC$, then $A$ $\in$ $NP$
- Here, we cannot say $A$ is $NPC$. All we can say is $A$ cannot be harder than $NPC$ and hence $NP$ (all $NPC$ problems are in $NP$). To belong to $NPC$, all $NP$ problems must be reducible to $A$, which we cannot guarantee from the given statement.
If $A$ is reduced to $B$, $C$ is reduced to $A$ , $B \in NP $ and $C \in$ $NPC$, then $A$ $\in$ $NPC$
- Here, the first reduction says that $A$ is in $NP$. The second reduction says that all $NP$ problems can be reduced to $A$ (because $C$ is in $NPC$, by definition of $NPC$, all problems in $NP$ are reducible to $C$ and now $C$ is reduced to $A$). Hence, the two necessary and sufficient conditions for $NPC$ are satisfied and $A$ is in $NPC$
If $A$ is reduced to $B$ and $B$ $\in$ $NPH$, then $A$ $\in$ $?$
- Here we can’t say anything about $A$. It can be as hard as $NPH$, or as simple as $P$.

8,651 total views, no views today

Discussion on Decidability

October 25, 2015 by Arjun Suresh Leave a Comment

Discussion on Decidability

October 25, 2015 by Arjun Suresh Leave a Comment

Direct Link

8,812 total views, 2 views today

Identify the Class of a Given Language

September 26, 2015 by Arjun Suresh 4 Comments

1 Given a description of a language $L$, how to find the class of $L$?
2 Some Facts
3 Some Twisted Examples

Given a description of a language $L$, how to find the class of $L$?

Find the set of strings generated by $L$

If the set of strings in $L$ is finite, $L$ is regular since all finite languages are regular
If the set of strings in $L$ is infinite, check if we can draw an NFA for recognizing $L$. If so, $L$ is regular
If $NFA$ is not possible for $L$, check if we can recognize $L$ using a $PDA$, that is with a stack in addition to set of states. If so, $L$ is $CFL$.
If the moves of $PDA$ are all deterministic, then $L$ is a $DCFL$
If $PDA$ is not possible for $L$, see if we can get a $TM$ for $L$
If $TM$ takes only a linear space (in terms of length of input string), then $L$ is $CSL$. otherwise its just recursive
If $L$ is a decision problem and $TM$ can just say “yes” and may not halt in case of “no”, then $L$ is recursively enumerable (partially decidable).
If $TM$ can say both “yes” and “no” then $L$ is recursive
If no $TM$ is possible for $L$, then $L$ is undecidable

Some Facts

Partially undecidable or semi-undecidable is considered undecidable. For example halting problem is considered undecidable but is semi-decidable.
$P$, $NP$ and $NPC$ problems can all be decided by a $TM$ and hence are recursive.
All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable.
Turing decidable problems are recursive but Turing recognizable (Turing acceptable) problems are only recursively enumerable.

Some Twisted Examples

1. $L = \{ww \mid w ∈ (a+b)^*\}$

The set of strings in $L$ are $\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, …\}$. We cannot accept these strings using an $NFA$. Now, even a $PDA$ is not possible as once we store $w$ on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize $L$. Now, $L$ can be accepted by a $TM$ in linear space and hence $L$ is $CSL$.

2. $L = \{ww\mid w ∈ (a+b)^+\}$

Same explanation as above, $L$ is $CSL$.

3. $L = \{ww_R\mid w ∈ ({a+b})^*\}$

$ww_R$ can be accepted by a $PDA$ and hence is $CFL$. But we need a $NPDA$ for this as there is no deterministic way to identify where $w$ ends and $w_R$ starts. $wcw_R, w\in(a+b)^*$ is accepted by a $DPDA$ and hence is $DCFL$.

4. $L = \{ww_R\mid w ∈ ({a+b})^+\}$

Same explanation as above. $L$ is $CFL$.

5. $L = \{wxw \mid w,x ∈ ({a+b})^*\} $

$L$ is regular since $ L = \Sigma^*$, by making $x = (a+b)^*$ and $w = \epsilon$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, …\} = \Sigma^*$

This language is different from the $L = \{wcw \mid w ∈ ({a,b})^*\} $ which is clearly a CSL. Here, we cannot do any reduction and hence there is no way to accept a string without checking w before c and w after c are the same which requires an LBA.

6. $L = \{wxw\mid w,x ∈ ({a+b})^+\}$

$L$ doesn’t contain all strings in $\Sigma^*$ as the strings like $abab$ are not contained in $L$. All words starting and ending in $a$ or starting and ending in $b$ are in $L$. But $L$ also contains words starting with $a$ and ending in $b$ like $abbab, aabbbabaab$ etc where the starting sub-string exactly matches the ending sub-string and at least a letter separates them. To accept such strings we need a $TM$ with linear space (this is at least as hard as accepting $ww, w \in (a+b)^*$), making $L$, a $CSL$.

7. $L = \{wxw_R\mid w,x ∈ ({a+b})^*\}$

$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*$, making $L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, …\} = \Sigma^*$

This language is different from the $L = \{wcw_R \mid w ∈ \{{a,b}\}^*\} $ which is clearly a DCFL. Here, we cannot do any reduction and hence there is no way to accept a string without checking that the string after c is the reverse of the string before c, which requires a DPDA.

8. $L = \{wxw_R\mid w,x ∈ ({a+b})^+\}$

The set of strings in $L$ are $\{aaa, aba, aaaa, aaba, abaa, abba, baab, …\}$ i.e.; $L$ contains all strings starting and ending with $a$ or starting and ending with $b$ and containing at least 3 letters. Moreover, $L$ doesn’t contain any other strings. Thus $L$ can be accepted by a finite automata making $L$ regular . Regular expression for $L$ is $a(a+b)^+a + b(a+b)^+b$.

9. $L = \{wxwy \mid w,x,y ∈ ({a+b})^+\}$

For any string to be in $L$, the beginning part of the string ($w$) must repeat at some other point (between the second and last characters) of the string (next $w$). Since $y$ is there at the end which can generate any string, we can make $w$ as small as possible as per the given condition. So, $w$ can be either $a$ or $b$. We can thus write regular expression for $L$ as $a(a+b)^+a(a+b)^+ + b(a+b)^+b(a+b)^+$

10. $L = \{xwyw \mid w,x,y ∈ ({a+b})^+\}$

Similar explanation for example 9, except that instead of first character being $a$ or $b$ we have the last character. So, regular expression for $L$ will be
$(a+b)^+a(a+b)^+a + (a+b)^+b(a+b)^+b$

11. $L = \{wxyw \mid w,x,y ∈ ({a+b})^+\}$

Here, $w$ is coming at the beginning and also at the end. Unlike as in example 8 or 9, we cannot restrict $w$ to be $a$ or $b$ as a string starting with $a$ can end in $b$ and still be in $L$- example $abaaab$, where $w = ab$ and $x,y = a$. In short we need to compare the substring at the beginning of the string with that at the end, making this a CSL.

12. $L = \{xww \mid w,x ∈ ({a+b})^*\}$

$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*$, making $L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, …\} = \Sigma^*$

13. $L = \{xww \mid w,x ∈ ({a+b})^+\}$

Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of an LBA making $L$ a CSL.

14. $L = \{xww_R \mid w,x ∈ ({a+b})^+\}$

Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of a PDA making $L$ a NCFL (non-determinism is required to guess the start of $w$).

18,801 total views, 3 views today