Complexity Theory — Free Notes & Tutorial
Free Complexity Theory notes for BTech CS — Big-O, P vs NP, NP-completeness, polynomial reductions, Turing machines, Cook–Levin theorem, SAT, 3-SAT, CLIQUE, PSPACE, approximation algorithms and interactive proofs, with exam-ready proofs. 100% free. Free Complexity Theory course on SikshaSarovar.
This Complexity Theory course is part of Siksha Sarovar and is 100% free for students in India — no sign-up required to read. It contains 15 structured lessons with examples, and pairs with our free online compiler and AI tutor.
What you will learn
- Big-O notation
- Time complexity
- Space complexity
- P
- NP
- NP-hard
- NP-complete
- Reductions
- Turing machines
- Non-determinism
- Cook–Levin theorem
- SAT
- 3-SAT
- CLIQUE
- Vertex cover
- PSPACE
- TQBF
- Approximation algorithms
- Interactive proofs
Course content (15 lessons)
- Course Introduction: The Science of Hard Problems — Welcome to Complexity Theory Algorithms courses ask: how fast can we solve this problem? Complexity theory asks the deeper question: how fast can this problem possibly be solved —…
- Unit 1: Time & Space Complexity and Big-O Notation — 1.1 What exactly are we measuring? For an algorithm A and input of size n (bits, array length, number of vertices — state your convention!): Time complexity T(n): the maximum…
- Unit 1: The Complexity Classes — P, NP, NP-Hard, NP-Complete — 2.1 Class P — solvable fast P = the class of decision problems (languages) decidable by a deterministic algorithm in polynomial time , i.e. time O(nᵏ) for some constant k.…
- Unit 1: Polynomial-Time Reductions — 3.1 The idea: solving A by translating it into B A polynomial-time (many-one/Karp) reduction from A to B, written A ≤ₚ B , is a function f computable in polynomial time such that…
- Unit 2: Turing Machines & Their Variants — 1.1 Why we need a formal machine Statements like "no polynomial algorithm exists" quantify over all possible algorithms — impossible unless "algorithm" has a mathematical…
- Unit 2: Non-deterministic Computation — 2.1 The non-deterministic Turing machine (NTM) One change to the model: the transition function returns a set of possible moves — δ : Q × Γ → 𝒫 (Q × Γ × {L, R}) At each step the…
- Unit 2: Circuit Complexity & Random Access Machines — 3.1 Boolean circuits — hardware as a complexity model A Boolean circuit with n inputs is a directed acyclic graph whose internal nodes ( gates ) are labelled AND (∧), OR (∨), NOT…
- Unit 2: Complexity of Concrete Algorithms — Sorting, Searching, Graphs — 4.1 Searching Algorithm Requirement Time Space :--- :--- :--- :--- Linear search none O(n) O(1) Binary search sorted array O(log n) O(1) Hash table lookup hash function O(1)…
- Unit 3: The Cook–Levin Theorem — 1.1 The statement Cook–Levin Theorem (1971/1973). SAT — the satisfiability problem for Boolean formulas in CNF — is NP-complete . This is the keystone: the first problem proved…
- Unit 3: The Classic NP-Complete Problems — SAT, 3-SAT, CLIQUE — 2.1 SAT — the root problem SAT: given a CNF formula φ — an AND of clauses , each an OR of literals (a variable or its negation) — does an assignment make φ true? NP-complete by…
- Unit 3: Techniques for Proving NP-Completeness — 3.1 The standard recipe (write it at the top of every answer) To prove problem B NP-complete: 1. B ∈ NP. Name the certificate; argue the verifier is polynomial. (One sentence —…
- Unit 4: P vs NP — The Problem and the Consequences of P = NP — 1.1 The statement P vs NP: Is P = NP? Equivalently: can every problem whose solutions are quickly verifiable also be quickly solved ? Equivalently (via Cook–Levin): does SAT have…
- Unit 4: PSPACE & Complexity Beyond Polynomial Time — 2.1 PSPACE — polynomial memory, unlimited patience PSPACE = problems decidable using polynomial space (memory), with no time restriction. NPSPACE = the non-deterministic version —…
- Unit 4: Living with Hardness — Approximation Algorithms & Interactive Proofs — 3.1 NP-hard in practice: the coping strategies P ≠ NP (presumably) forbids only exact + worst-case-fast + general . Drop any one: Drop Strategy Example :--- :--- :--- exactness…
- Quick Revision & Exam Preparation — The 20 definitions you must write precisely 1. f = O(g): ∃ c, n₀ 0 : f(n) ≤ c·g(n) ∀ n ≥ n₀ (Ω: ≥; Θ: both). 2. Time/space complexity: worst-case steps / cells used as a function…
Course Introduction: The Science of Hard Problems
Welcome to Complexity Theory
Algorithms courses ask: how fast can we solve this problem? Complexity theory asks the deeper question: how fast can this problem possibly be solved — by any algorithm, ever? It is the study of the inherent difficulty of computational problems, and it contains the most famous open question in computer science: does P equal NP?
The journey of this course
How this course is organised
| Syllabus block | Lessons that cover it |
|---|---|
| Basics of computational complexity, time & space complexity, Big-O | Unit 1 → "Time, Space & Big-O Notation" |
| Problem classification: P, NP, NP-hard, NP-complete | Unit 1 → "The Complexity Classes" |
| Polynomial-time reductions (introduction) | Unit 1 → "Polynomial-Time Reductions" |
| Turing machines and variants | Unit 2 → "Turing Machines & Their Variants" |
| Non-deterministic computation | Unit 2 → "Non-deterministic Computation" |
| Circuit complexity, random access machines | Unit 2 → "Circuit Complexity & the RAM Model" |
| Complexity of sorting, searching, graph algorithms | Unit 2 → "Complexity of Concrete Algorithms" |
| Cook–Levin theorem | Unit 3 → "The Cook–Levin Theorem" |
| SAT, 3-SAT, CLIQUE | Unit 3 → "The Classic NP-Complete Problems" |
| Techniques for proving NP-completeness | Unit 3 → "Proving NP-Completeness" |
| P vs NP statement & consequences of P = NP | Unit 4 → "P vs NP & What P = NP Would Mean" |
| PSPACE and other classes, beyond polynomial time | Unit 4 → "PSPACE & the Wider Class Zoo" |
| Approximation algorithms, interactive proofs | Unit 4 → "Living with Hardness" |
Why this subject matters to you
- It tells you when to stop looking for a fast algorithm. Recognising that a scheduling/routing/packing problem is NP-complete saves weeks of doomed optimisation and points you to approximations and heuristics instead.
- It underpins security. All of modern cryptography rests on complexity assumptions — RSA is safe only because we believe factoring is hard.
- It is a placement/interview differentiator. "Is this problem NP-complete, and how would you cope?" is a real senior-engineer interview question.
- It is intellectually spectacular. P vs NP carries a million-dollar prize and would reshape mathematics, AI and medicine if resolved.
Prerequisites
| You should know | Why |
|---|---|
| Asymptotic notation from Data Structures | We sharpen and formalise it |
| Basic graph terminology (vertex, edge, path, clique) | Reductions live on graphs |
| Propositional logic (AND/OR/NOT, truth t
Continue reading: Course Introduction: The Science of Hard Problems →
Frequently asked questions
Is the Complexity Theory course really free?
Yes. The entire Complexity Theory course on Siksha Sarovar is free to read with no account required. You can optionally sign in with Google to save your progress.
Do I get a certificate for Complexity Theory?
Yes — finish the lessons and pass the quiz to earn a free, verifiable certificate you can share on LinkedIn or with recruiters.
Can I run code while learning?
Yes. The built-in online compiler runs C, C++, Python, Java, PHP, JavaScript, C# and SQL directly in your browser — no installation needed.