31 questions · 11 sources · 0 syntheses
Computational Complexity Theory
Classifying computational problems by resource requirements.
Source-derived questions
Questions extracted from the papers in this topic, excluding the curated questions above.
- How can a nondeterministic finite automaton be converted into a deterministic one without losing expressive power?
- How did Cook's proof show that many seemingly unrelated hard computational problems were secretly versions of the same problem?
- How did Manuel Blum help define what it means for an encryption scheme to be secure?
- How did Rabin and Scott's result seed later work on regular expressions and the P versus NP problem?
- How did the classification of a problem as NP-complete change how computer scientists approach solving it?
- How do Yao's circuit complexity results limit restricted models of computation?
- How does Karp's result relate to the still-unsolved P versus NP problem?
- How does PAC learning define when a system can be said to have learned something?
- How does complexity theory explain why cryptographers trust certain codes to be practically unbreakable?
- How does derandomization let algorithms replace true randomness with pseudorandom bits?
- How long did it take the field to award Hartmanis and Stearns the Turing Award after their paper?
- What assumption about nondeterministic machines did Rabin and Scott disprove in their 1959 paper?
Show 19 more questions
- What did Hartmanis and Stearns's 1965 paper introduce that founded computational complexity theory?
- What does Yao's minimax theorem prove about randomised algorithms?
- What does computational complexity theory actually measure about a problem?
- What does it cost, in terms of number of states, to convert a nondeterministic automaton into a deterministic one?
- What does it mean for a problem to be NP-complete, and how did Karp prove twenty-one problems belonged to that class?
- What does it mean that randomness and computational hardness are equivalent in Avi Wigderson's work?
- What graph problems did theoretical computer science struggle to solve efficiently before Hopcroft and Tarjan's work?
- What is a pseudorandom number generator, and why does modern cryptography depend on it?
- What is communication complexity theory and what question does it ask?
- What is planarity testing and why did Hopcroft's efficient algorithm for it matter?
- What is the Boolean satisfiability problem, and why is it considered NP-complete?
- What is the P versus NP question, and why does it remain unsolved?
- What problem in machine learning did Leslie Valiant's PAC learning framework solve?
- What real-world fields, like cryptography, would be affected if someone proved P equals NP?
- What theoretical foundations did Turing's 1936 paper lay for computation, years before the machines it described could be built?
- Why did pre-1984 cryptography rely on computational hardness rather than physical laws for its security guarantees?
- Why does proving one NP-complete problem has a fast algorithm imply fast algorithms exist for all of them?
- Why is P versus NP considered the most consequential unsolved problem in theoretical computer science?
- Why is Valiant's 1984 framework still relevant to modern neural networks?