• quilan@lemmy.world
    link
    fedilink
    arrow-up
    15
    ·
    edit-2
    8 months ago

    For the purposes of OPs problem (P v NP), it considers not particular solutions, but general algorithmic approaches. Thus, we consider things as either Hard (exponential time, by size of input), or Easy (only polynomial time, by size of input).

    A number of important problems fall into this general class of Hard problems: Sudoku, Traveling Salesman, Bin Packing, etc. These all have initial setups where solving them takes exponential time.

    On the other hand, as an example of an easy problem, consider sorting a list of numbers. It’s really easy to determine if a lost is sorted, and it’s always relatively fast/easy to sort the list, no matter what setup it had initially.