What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems? Before asking the question, I should say that I am not sure here is a proper community to ask this question or not.
I have an NP-hard problem and an optimization to deal with the problem. Recently, I have found that the problem has a phase transition where, before a threshold for a property,  the problem can be solved in polynomial time by a greedy approach and, difficult cases are after the threshold.
Now, I want to show this phase transition by some parameters related to the optimization that solves the problem. But, I don't know which parameters can show this phase transition in a valid way, like time-solving, the number of iterations to solve the problem, or .....
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.