Blog Archives

Time and Space Complexity Class

Robust classes are those such that no reasonable changes to the model of computation should change the class; capable of classifying interesting problems. Examples \(\mathsf{L}\) (contains Formula Value, integer multiplication and division), \(\mathsf{P}\) (contains circuit value, linear programming, max flow),

Posted in Theory

Pairwise Independence

A collection of random variables is pairwise independent if every pair of variables are independent. Given \(k\) independent bits, we define \(n = 2^k-1\) random variables each of which is a parity of a non-empty subset of the \(k\) bits.

Tagged with: , , ,
Posted in Theory

Knapsack

The Knapsack problem is defined as follows. Given a set of \(n\) items \(i=1,\ldots, n\), each with weight \(w_i\) and value \(v_i\), and a knapsack capacity \(C\), find a subset of items such that the total weight is bounded by

Tagged with: , , , ,
Posted in Theory

Context-Free Languages

A context-free grammar is a tuple \(G=(V, \Sigma, P, S)\) where \(V\) is a finite set of variables, \(\Sigma\) is an alphabet with a finite set of symbols which are called terminals, \(P\) is a finite set of production rules,

Tagged with: , , ,
Posted in Theory