What is the discrete logarithm assumption and why it is not easy with Shank's baby-step/giant-step When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time. But I also read that there are several algorithms in $\mathcal{O}(\sqrt{n})$, for instance, the Shank's baby-step/giant-step so there must be some misunderstanding by me.


What is the assumption?


If I understand the problem correctly, we are given a group with a modulus and a generator of that group. The problem is: 


Given an element $x$ of the group, find the number $a$ so that the generator $g$ will generate $x$ by $$x = g^a \bmod q.$$ And the assumption is that we cannot do it for a random or worst instance of the problem in polynomial time, but I must have misunderstood because I read about deterministic algorithms such as Shank's baby-step/giant-step which solve the problem in $\mathcal{O}(\sqrt{|G|})$ which is quite fast isn't it?


Where is my mistake?
When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time.


Actually, whether or not we assume that it is hard depends on the group; there are certainly groups where it is quite easy (for example, in $\mathbb{Z}_q^*$ where $q-1$ is smooth).


  But I also read that there are several algorithms in O(sqrt(n)) for instance the big-step/baby-step so there must be some misunderstanding by me.


That is what you are misunderstanding; when we say "polynomial time", we mean "polynomial in $\log(n)$"; $\sqrt{n}$ is not polynomial in $\log(n)$ (actually, it is exponential), and so that is not a contradiction.


  The problem is: Given an element $x$ of the group, find the number $a$ so that the generator $g$ will generate $x$ by $x = g^a \bmod q$.


Actually, there are a number of generalizations, and they're all sometimes called DLP:


Perhaps we don't require $g$ to be the generator of the entire group; we still insist that $x$ be a member of the subgroup that $g$ generates (there won't be an $a$ otherwise).  This is actually more common than your meaning; where $g$ might generate a prime-sized subgroup.
Perhaps we don't restrict ourselves to groups of the form $\mathbb{Z}_q^*$, but instead have $g$ and $x$ be members of a different group (for example, an elliptic curve group).  Sometimes this is called the ECDLog problem; sometimes, we aren't as specific.



  I read about deterministic algorithms such as Shank's which solve the problem in O(sqrt(|G|) which is quite fast isn't it?


Not if $|G| &gt; 2^{256}$, it's not (and yes, that's the size of the groups we use in practice)