2
$\begingroup$

Problems in $P$ have polynomial time algorithms. Problems in e.g. $NP-complete$ are only solvable in "probably exponential time" (Shen Lin's PET).

Problems in $P$ are considered easy while others (most likely) are not.

What does easy mean? I've always thought of hard and easy this way:

Our computing power grows exponentially over time. A problem is called easy if we can solve exponentially more instances of it (in reasonable time) after each time unit. A problem is hard if we can only solve polynomialy more instances of it after each time unit.

I'm well aware of complexity analysis, the definitions and their meaning. I'm trying to propose a reasonable, intuitive and easy to understand explanation of hard and easy. Would the explaination above explain it correctly and would someone who never heard of the subject understand it?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Community votes, please: is this a duplicate? $\endgroup$
    – Raphael
    Commented Mar 24, 2016 at 10:56
  • $\begingroup$ No. I'm trying to ask if given informal, intuïtive definition is reasonable or not. I'm well aware of most common complexity classes and their definition/meaning $\endgroup$
    – Auberon
    Commented Mar 24, 2016 at 11:46
  • $\begingroup$ But that's exactly what's been asked and answered there! (Maybe you need to change your title.) $\endgroup$
    – Raphael
    Commented Mar 24, 2016 at 13:09
  • 1
    $\begingroup$ You seem to be essentially postulating a fixed amount of time that every problem instance must be decided in, then ask what happens to the number of decided instances as this time bound is doubled. Assuming that the language contains $2^{\Omega(n)}$ instances of size $n$, this just gives the usual definition of polynomial and exponential runtime. However, your definition will also conclude that all sparse and tally languages are hard, even trivial ones. So it might feel "engineering right" but it is mathematically wrong. $\endgroup$
    – András Salamon
    Commented Mar 24, 2016 at 20:44

1 Answer 1

Reset to default
3
$\begingroup$

Your definition of "easy" doesn't make much sense. What exactly does "solving more instances at each time unit" mean?

Usually our notion of hardness refers to our ability to "solve" one instance. More formally, let $T(n)$ be the amount of operations required (proportional to time) for inputs of size $n$, then by "hard" we usually mean that $T$ grows too fast.

As for why polynomial $T(n)$ is considered easy, see this question.

Improve this answer
$\endgroup$

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