CSC 341 (Fall 2021)

Lab: Complexity Wrap-Up

Problem: Complexity Soup

In our unit on complexity, we have explored a number of complexity classes. Write down the “state of the world” as we understand it regarding the connection between the various complexity classes in question. For each complexity class, write down the canonical problem that is complete for the class to get a sense of what kinds of problems exist in that class.