Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Explore the fundamental limitations of computational complexity theory and data storage systems in this 54-minute German conference talk. Delve into why interesting problems are typically difficult to solve and how complexity theory helps identify which languages, methods, and data representations can effectively address these challenges. Learn about the critical category of NP-hard problems and their relationship to Boolean satisfiability (SAT), discovering why these problems can be reduced to satisfiability of groups with at least three variables (3-SAT) but not to groups with only two variables (2-SAT). Examine practical applications including scheduling problems where speakers give more than two presentations, and understand the hidden patterns that explain why key-value stores, despite their efficiency, cannot replace the need for triplet stores or more general relational databases when storing complex knowledge structures.
