The author defines
polynomial time algorithm as
algorithm
that on input of size $n$, has a worst-case running time of $O(n^k)$ where $k$ is any constant. The author describes that not all the problems can be solved in polynomial time. The author then focuses on "NP-complete" problems, the problems for which no polynomial time
algorithm
exists and nobody has been able to prove that no polynomial time
algorithm
can exist.
The author defines an
abstract problem to be a binary relation on a set $I$ of problem instances and a set $S$ of problem solutions. An instance of a SHORTEST-PATH problem is a triple with a graph and two vertices while its solution is a sequence of vertices in the graph.
The authors provide definitions of alphabet and language. The authors also define operations such as
union and
intersection. The authors then define
concatenation,
closure/Kleene star, and
complement. The author explains the meaning of an
algorithm
accepting a string and the language defined by acceptance of set of strings.
The author then calls a language decided by an
algorithm
$A$ if every binary string in $L$ is accepted by $A$ and every binary string not in $L$ is rejected by $A$.
A language $L$ is decided in polynomial time by an
algorithm
$A$ if there is a constant $k$ such that for any length-n string $ x \in L $, algorithm $A$ accepts $x$ in time $O(n^k)$. A language $L$ is decided in polynomial time by an algorithm $A$ if there is a constant $k$ such that for any length-n string $x \in \{0,1\}*$, the algorithm correctly decides whether $x \in L$ in time $O(n^k)$.
The author defines
Hamiltonian Cycle and
Hamiltonian Graph. A verification
algorithm
takes two arguments, an ordinary input string $x$ and a binary string $y$ called
certificate. The
algorithm
$A$ verifies the input string $x$ if there exists a certificate $y$ such that $A(x,y)=1$.
The authors define
complexity class NP as the class of languages that can be verified by a polynomial time
algorithm
. The complexity class co-NP is defined as set of languages $L$ such that $\overline{L} \in NP$.
A language $L_1$ is called
polynomial time reducible to a language $L_2$, written $L_1 \le _P L_2$, if there exists a polynomial time computable function $ f : \{0,1\}* \rightarrow \{0,1\}* $ such that for all $ x \in \{0,1\}* $, $ x \in L_1 $ if and only if $ f(x) \in L_2$. $f$ is called the
reduction function and a polynomial time
algorithm
$F$ that computes $f$ is called
reduction algorithm.
A language $L \subseteq \{0,1\}*$ is
NP-complete if
- $L \in NP$, and
- $L' \le _P L$ for every $L \in NP$.
If a language $L$ satisfies property 2, but not necessarily property 1, we say that $L$ is
NP-hard.
A
truth assignment for a boolean combinational circuit is a set of boolean input values. A one output boolean combinational circuit is
satisfiable if it has a
satisfying assignment, a truth assignment that causes the output of the circuit to be 1.
The
circuit-satisfiability-problem is to determine whether a boolean combinational circuit composed of AND, OR and NOT gates satisfiable.
The
size of a boolean combinational circuit is the number of boolean combinational elements plus the number of wires in the circuit. The authors then prove two lemmas based on which they derive the theorem that circuit-satisfiability-problem is NP-complete.
The author prove a Lemma and a theorem to show that satisfiability of boolean formulas is NP-complete.
The authors then discuss following problems to be NP-complete:
- The clique problem
- The vertex-cover problem
- The hamiltonian-cycle problem
- The travelling-salesman problem
- The subset-sum problem
for vertex cover problem and prove that it is a polynomial time 2-approximation algorithm
.
.
:
to determine if any of the segments intersect, prove its correctness and proves its running time to be $O(n \lg n)$.
and discuss following four algorithms with text length of $n$ and pattern length of $m$:
. The author provides division theorem, then proves it. The author defines remainders, common divisors and greatest common divisors, relatively prime integers
and unique factorization.
and provides prime number theorem
which provides details of density of prime numbers. The author provides pseudo-primality test
and miller-rabin randomized primality test
.
and provides Pollard's rho heuristic.
(FFT
). The author defines a polynomial of variable $x$ over a field $F$. The author defines coefficients of the polynomial and degree of a polynomial. The author defines two operations; polynomial addition and multiplication.
, (DFT
) and then show how the FFT
computes the DFT
and its inverse in $O(n \lg n)$.
implementation and a parallel FFT
circuit.
. The authors define the concepts of linear function, linear equality and linear inequality and linear programming
problem. The author defines feasible region, feasible solution, objective solution and objective value.
ranging from operations research, solving graph and combinatorial problems. The author then discusses algorithms
like ellipsoid algorithm