0
$\begingroup$

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 .....

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

There is no contradiction. NP-hard does not mean "large instances can't be solved quickly", rather, it means "there is an infinite number of instances that are hard". 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Isn't it that an impression of being NP-hard or NP-Complete is that there is not any polynomial approach to solve the problem and the complexity increases exponentially with the size of the input? $\endgroup$
    – samie
    Dec 4, 2020 at 14:43
  • 1
    $\begingroup$ It is believed that there is no polynomial time algorithm which is fast on every instance. It is perfectly possible to be fast on some instances (and indeed, this is not at all unusual). $\endgroup$
    – Juho
    Dec 4, 2020 at 15:46
  • $\begingroup$ and finally, could you say me what does mean "hard" and "easy" in your definition of instances in NP-hard problems? $\endgroup$
    – samie
    Dec 4, 2020 at 16:23
  • $\begingroup$ Ok, I've got it. Let me modify my question. Is it possible to find that an instance is easy or difficult by the associated optimization which is created to solve the problem? I mean, maybe in difficult instances, the optimization must check all possible solutions to find the optimal one, so it needs many more iterations than easy instances. Actually, I want to find a relation between instances (difficult or easy) and the parameters in optimization. $\endgroup$
    – samie
    Dec 5, 2020 at 6:49
  • $\begingroup$ Yes, but we are talking about a given algorithm. It does not matter X is faster than Y. We want to compare the number of iterations between easy instance A and hard instance B in a given algorithm X. The comparison will be correct for instances A and B in algorithm Y on a different scale. Consider that the number of iterations is just an assumption and, I don't know what parameter of optimization can make this comparison for instances. $\endgroup$
    – samie
    Dec 5, 2020 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.