## 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