Computational Complexity
Big –O notation
A function f(n) is of the order of g(n) if 2 constants n0 and
K can be found , such that the following proposition is
true:
for all n ≥ n0 : f(n) ≤ K g(n)
Example:
f((n) = 3n + 2 = O(n) …as 3n+2 ≤ 4n for all n ≥ 2
f(n) = 10n2+4n+2 =O(n2) as 10n2+4n+2 ≤ 11n2 for all n ≥5
f(n) = 10n2+4n+2 =O(n4) as 10n2+4n+2 ≤ 10n4 for all n ≥2
Running time of algorithms
Models for Computation
Mathematician- David Hilbert
Entsheidungsprobleme
Whether or not there exists some algorithm which
could be used, in principle, to solve all the
problems of mathematics
Answe NO!
r
Turing Machine – a model for a
programmable computer
Turing’s work lead to the development of the John von
Neumann model of a practical computer (hardware)
Church-Turing Thesis
The class of functions computable by a
Turing machine corresponds exactly to the
class of functions which we would naturally
regard as being computable by an
algorithm
Question
Does there exist in Nature a process which
computes a function not computable by a
Turing machine?
Universal Turing Machine
• A machine that can be used to simulate
any other Turing machine
• UTM completely captures the meaning of
performing a task by algorithmic means
(Church-Turing thesis)
Efficiency
• Strong Church-Turing thesis- Any
algorithmic process can be simulated
efficiently using a Turing machine
• Analog Computation – seems to
challenge strong Church-Turing thesis.
Noise considerations must be made
• Randomized Algorithms- Any algorithmic
process can be simulated efficiently using
a probabilistic Turing machine
Types of Algorithms
• Deterministic
• Non-deterministic ( Randomized or
Probabilistic)
• Heuristic ( Insight or Intuition)
Strong Church-Turing thesis
Any model of computation can be simulated
on a probabilistic Turing machine with at
most a polynomial increase in the number
of elementary operations required
Problem and instance
A problem is an abstract description ; for example, the Traveling
Salesman Problem (TSP) is: “Given a graph with nodes and edges
and costs associated with the edges, what is a least-cost closed walk
(or tour) containing each of the nodes exactly once?”
Instance
• Find the shortest
path covering nodes
‘a’,’b’,’c’ and ‘e’
Continuous vs combinatorial/discrete
• Instances of optimization problem can be characterized
by a finite set of variables; the correct choice for the
values of these variables specifies the optimal solution
• Continuos optimization – variables range over real
numbers
• Discrete optimization- variables assume a finite number
of distinct values
• CAD for VLSI- combinatorial optimization
Decision version of a problem
• Given an instance of a combinatorial optimization
problem, the goal is to find the feasible solution with
minimal cost
• Decision problems – yes or no answer to the problem
• An optimization problem can be re-framed as a decision
problem:
• Is there a solution with cost < K?
• Which is easier? Optimization version or decision
version of a problem say, TSP
Complexity classes
• Suppose one could solve the optimization version in
polynomial time, then the decision version can also
be solved in polynomial time
• Not true other way round.
• Deterministic and non-deterministic machine/
computer
– Non-deterministic –
Conceptual tool to analyze complexity of
algorithms
Machine that splits itself into as many copies as
needed, evaluates in parallel and merges back into 1
machine
Class P and NP
• Class P consists of those problems that can be solved in
polynomial time in a deterministic machine (eg.a conventional
computer).
• Eg. Minimum cost spanning tree, single source shortest path and
graph matching problems
Class P and NP
• Class NP (non deterministic polynomial)
consists of problems that can be solved in
polynomial time by a non deterministic
machine
• All algorithms which run in polynomial time
on a deterministic computer will certainly
execute in polynomial time on a non
deterministic one
Class NP-complete and NP-hard
• Class NP-complete(NPC) is characterized by
the fact that all decision problems contained
in it are polynomially reducible to each
other.
• An instance of any NPC problem can be
expressed as an instance of any other NPC
problem using transformations that have
polynomial time complexity.
• The optimization version of a problem is
called NP hard if the decision version of the
problem is NP-complete
Some NP-complete problems
• Boolean satisfiability problem (SAT)
• Knapsack problem
• Hamiltonian path problem
• Travelling salesman problem (decision version)
• Subgraph isomorphism problem
• Subset sum problem
• Clique problem
• Vertex cover problem
• Independent set problem
• Dominating set problem
• Graph coloring problem
Million dollar question!
https://www.claymath.org/millennium-problems/
NP-complete
Channel routing is NP-complete
So what is the issue now?
• Most optimization problems in VLSI physical design are
NP-complete or NP-hard
• It is unlikely that a polynomial time algorithm exists to
solve them.
• This is because of the large no of components(n > 106 )
that we must deal with in VLSI(eg.an algorithm which
must operate on a layout)
• Heuristics – only way
• A heuristic is a technique designed for solving a
problem more quickly when classic methods are too
slow, or for finding an approximate solution when classic
methods fail to find any exact solution.
• Heuristics use educated guess, intuition
Heuristic Algorithms
• Deterministic
• Stochastic
Structurally
- Constructive (Start with a partial solution
and build/ add components)
- Iterative ( Start with an initial solution and
then improve the solution)
Constructive + Iterative
Heuristic Algorithm
