Complexity class facts for kids

A Complexity class is a concept from theoretical computer science and mathematics: All problems that have the same complexity are in the same complexity class. This means, that for a given input, they need about the same amount of resources, such as compute time, or memory. The most often used models for complexity are time complexity, which measures the time needed to calculate a result, or space complexity, which looks at the amount of memory or storage needed. When talking about complexity classes, a worst case scenario is usually assumed.

Images for kids

• 

  Example Boolean circuit computing the Boolean function f_C(x_1,x_2,x_3)=\neg (x_1 \wedge x_2) \wedge ((x_2 \wedge x_3) \vee \neg x_3), with example input x_1=0, x_2=1, and x_3=0. The \wedge nodes are AND gates, the \vee nodes are OR gates, and the \neg nodes are NOT gates.

See also

In Spanish: Clase de complejidad para niños