What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems?
There is no contradiction. NP-hard does not mean &quot;large instances can't be solved quickly&quot;, rather, it means &quot;there is an infinite number of instances that are hard&quot;. Large instances can be easy while small instances can be hard - it's the structure that counts and not size. Put differently, if a problem is NP-hard, it is believed that there is no algorithm which runs in polynomial-time (and is correct) on every instance. It is perfectly possible to have algorithms that are fast on particular instances.
So perhaps you misunderstood what phase transition means. Nevertheless, if you want to learn more about it, remember that it is relevant only for random instances.