Conversation

So here’s what each term means

• P: problems which can be done by a deterministic Turing machine (always knows it will finish) in polynomial time (more or less manageable, doesn’t quickly become ridiculously hard like e.g. exponential time)
• NP: problems which can be done by a non-deterministic Turing machine (might get stuck in a loop, so just like your computer) in polynomial time, what’s called “bruteforcing” – deterministic Turing machines can only prove in polynomial time that they can be solved
• P versus NP: Are all NP problems actually P problems under disguise? Can every single problem that can be done “quickly” also be done in a deterministic Turing machine? Can we avoid bruteforcing and prove that we’ll always get a solution in due time? Is P a subset of NP, or are they one and the same?
• NP-complete: a kind of NP problems which every other NP problem can be converted into by “transforming” aka “reducing” – to figure out if they can always be timely solved, you need to know if every other NP problem can be solved in polynomial time as well, thus if P=NP (SAT solvers can handle these)
• NP-hard: problems for which we have no idea if they can be solved in polynomial time (they’re hard :blobcatshrug: )

…is it normal that I struggled to get these :blobcatsweat: