Science Quiz / Complexity Classes

Random Science Quiz

Can you name the Complexity Classes?

 Plays Quiz not verified by Sporcle

How to Play
Support Sporcle.
Go Orange.
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

From the Vault

Marvel Superhero by Origin Story II

by BorezU

And now you can skip the corresponding movie.
Remove Ads.
Support Sporcle.
Get the best of Sporcle when you Go Orange. This ad-free experience offers more features, more stats, and more fun while also helping to support Sporcle. Thank you for becoming a member.

Show Comments

Extras

Created Nov 29, 2010ReportNominate
Tags:class, description

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.

Report this User

Report this user for behavior that violates our Community Guidelines.

Details: