Asklemmy

43989 readers

685 users here now

A loosely moderated place to ask open-ended questions

Search asklemmy 🔍

If your post meets the following criteria, it's welcome here!

Open-ended question
Not offensive: at this point, we do not have the bandwidth to moderate overtly political discussions. Assume best intent and be excellent to each other.
Not regarding using or support for Lemmy: context, see the list of support communities and tools for finding communities below
Not ad nauseam inducing: please make sure it is a question that would be new to most members
An actual topic of discussion

Looking for support?

Looking for a community?

Lemmyverse: community search
sub.rehab: maps old subreddits to fediverse options, marks official as such
[email protected]: a community for finding communities

~Icon~ ~by~ ~@Double_[email protected]~

founded 5 years ago

MODERATORS

[email protected]

231

Professional Scientists of Lemmy: What is your field of study's, most complex unanswered question? (lemmy.world)

submitted 6 months ago by [email protected] to c/[email protected]

110 comments fedilink hide all child comments

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 15 points 6 months ago* (last edited 6 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.