# Category:Theorems in computational complexity theory

Computing portal |

Here is a list of articles in the category **Theorems in computational complexity theory** of the Computing portal that unifies foundations of mathematics and computations using computers.

## Pages in category "Theorems in computational complexity theory"

The following 20 pages are in this category, out of 20 total.

### B

- Blum's speedup theorem
*(computing)*

### C

- Cook–Levin theorem
*(computing)*

### F

- Fagin's theorem
*(computing)*

### G

- Gap theorem
*(computing)*

### K

- Karp–Lipton theorem
*(computing)*

### L

- Linear speedup theorem
*(computing)*

### M

- Master theorem (analysis of algorithms)
*(computing)*

### N

- No free lunch in search and optimization
*(computing)*

### P

- PCP theorem
*(computing)* - Pseudorandom generator theorem
*(computing)*

### Q

- Quantum threshold theorem
*(computing)*

### S

- Savitch's theorem
*(computing)* - Schaefer's dichotomy theorem
*(computing)* - Sipser–Lautemann theorem
*(computing)* - Space hierarchy theorem
*(computing)* - Speedup theorem
*(computing)* - Structured program theorem
*(computing)*

### T

- Time hierarchy theorem
*(computing)* - Toda's theorem
*(computing)*

### V

- Valiant–Vazirani theorem
*(computing)*