Science Quiz / Complexity Classes

Random Science Quiz

Can you name the Complexity Classes?

Quiz not verified by Sporcle

How to Play
Challenge
Share
Tweet
Embed
Score 0/20 Timer 15:00
Class DescriptionComplexity Class
Solvable in polynomial time
Verifiable in polynomial time
Solvable in polynomial space
Solvable with bounded error in probabilistic polynomial time
Solvable with one-sided error in probabilistic polynomial time
Solvable with bounded error in quantum polynomial time
Solvable in expected polynomial time
Verifiable with bounded error in probabilistic polynomial time, interacting with a prover
Everything
Nothing
Class DescriptionComplexity Class
Verifiable with bounded error in probabilistic polynomial time
Solvable in logarithmic space
Verifiable in logarithmic space
Solvable with error less than 1/2 in probabilistic polynomial time
Solvable in polynomial time with polynomial advice
Solvable with constant depth circuits
Solvable in polynomial time with an oracle to SAT
Verifiable with bounded error in probabilistic polynomial time, interacting with multiple provers
Verifiable with bounded error in quantum polynomial time
Solvable in exponential time

You're not logged in!

Compare scores with friends on all Sporcle quizzes.
Sign Up with Email
OR
Log In

You Might Also Like...

Show Comments

Extras

Top Quizzes Today


Score Distribution

Your Account Isn't Verified!

In order to create a playlist on Sporcle, you need to verify the email address you used during registration. Go to your Sporcle Settings to finish the process.