TOC 7.3 (pp. 292-298) NP
- Due Nov 19, 2021 by 11am
- Points 21
- Submitting a text entry box or a file upload
- File Types pdf
Reference the text and watch this video made in collaboration with Scott Aaronson and the Complexity Zoo, then answer the following questions.
- Describe the class P simply, then in terms of asymptotic complexities.
- In your own words, what is the P vs NP question?
- What are the implications of P equals NP (why is it important).
- What are NP Complete problems? Give examples of problems/games.
- Why is it so hard to prove P equals NP?
- How much time is allowed for problems solved in PSPACE?
- How is P vs NP related to other sciences and arts?