Back to Discover
💻

Computational complexity theory

technology Maturity 11-13

Computers do many tasks. Some tasks are hard. They take a lot of time. They might use a lot of space. We study how hard they are. This helps us know what computers can do. Can you think of a hard task?

Turing machine 2b.svg
Turing machine 2b.svg

45 words
🖼️ Images & Media (6)
File:TSP Deutschland 3.png
TSP Deutschland 3.png
File:Decision Problem.svg
Decision Problem.svg
File:Turing machine 2b.svg
Turing machine 2b.svg
File:Sorting quicksort anim.gif
Sorting quicksort anim.gif
File:Complexity subsets pspace.svg
Complexity subsets pspace.svg
File:Complexity classes.svg
Complexity classes.svg
Up Next
💻
Theory of computation
Technology
→
More to explore

✨ What else?

Related topics you might enjoy

Theory of computation 0% Theoretical computer science 0% Model of computation 0% Time complexity 0% Space complexity 0% Nondeterministic Turing machine 0%

🔬 Go deeper

More advanced topics to explore

Theory of computation P (complexity) Theoretical computer science Model of computation

🪜 Step back

Simpler topics to build understanding

Computable function Oracle machine Turing reduction NP (complexity)
📚 Content adapted from Wikipedia | Readability: FK 13.6 | Vital Level 4