What is an 'NP-Hard' problem?
NP-Hard problems are at least as hard as NP-Complete problems, but may not lie within NP (can be non-decision or undecidable problems like Halting Problem).
What famous theorem established that the Boolean Satisfiability Problem (SAT) is NP-Complete?
Stephen Cook and Leonid Levin proved in 1971 that SAT is the foundational NP-Complete problem.
Which of the following decision problems is known to be NP-Complete?
3-SAT, TSP decision, Vertex Cover, and Clique are classic NP-Complete problems.
What is 'Polynomial-Time Reduction' (A $\le p B) used$ for?
If A $\le p B$ and A is NP-Hard, then B is also proved to be NP-Hard.
Is the Membership Problem for Context-Sensitive Languages (Type-1) Decidable?
Because an LBA tape is strictly bounded to k $\times |w|$, the total number of distinct configurations is finite (though exponential), making CSL membership decidable.