CSE4111 CSE4111/5111: Computability and Complexity

Readme, Course Information, Course Description, Dates, Photos Fun, Your Marks (4111,5111) Forum, Class

 Topics Slides Videos Steps Notes Questions Solutions Tests Quantifiers (Take up Exam Question.) Turing Machines Models of Computability Complexity Classes Diagitization & Uncomputability Reductions For Uncomputability No Proof System for Number Theory NP-completeness (sols) Other Possibilities

This course is an extention of 2001. It is useful for a student
interested in the theoretical aspects of computer science.

Request:

Texts:

Introduction: (ppt)

Quantifiers: (Steps, ppt, Questions)
(Before a student can understand or prove anything in mathematics, it
is essential to first be able to res present it in first order
logic. Hence, Jeff reviews it in each of his courses.)

Existential and Universal quantifiers

Turing Machines: (ppt, Questions)
(Historic and mathematical ways of modeling machines for computing.)

History & Overview
Church's Thesis
Goto vs Loop Models
Turing Machines
Loop Invariant Example
Table Lookup Example
Single vs Multi Tape TMs
Java to TM
Constant vs Finite vs Infinite
Universal TM

Other Models of Computability: (ppt, Cook, Questions)
(More Historic ways of modeling machines for computing.)

Primitive Recursive
TM to Primitive Recursive?
Primitive Recursive << TM
TM to Recursive
Register Machine
And/Or/Not Circuits
Computer Circuits
Circuits Depth
Arithmetic Circuits
Neural Nets
Poly-Time
Non-Deterministic Machines
Quantum Machine
Context Free Grammars
Java to Machine Code (Compiling/Parsing) (pdf, Java)
Context Sensitive Grammars
TM to Grammar
Decide vs Accept
Humans
Complexity Classes

Complexity Classes: (ppt, Questions)
(We classify computational problems based on the amount of resources
used to compute them.)

Computable using Halting as an oracle
Acceptable, Witness, Enumerable
Computable
Ackermann's Time
Double Exponential Time
E: Exponential Time
Exp Time
PSpace
PH: Poly-Time Hierarchy
NP & Co-NP
Poly-Time
NC: Poly-log depth Circuits
NC2
NL: Non-Det Log Space
L: Log-Space
AC0, Thres0, Arith0: Constant Depth
NC0: Constant Fan-out

Diagonization & Uncomputability: (ppt, Cook, Questions)
(There are more real numbers than fractions and the same number of
fractions as integers.)
(Some computational problems are solved by NO algorithms.)

Uncountable Infinity & Diagonalization
Diagonal Uncomputable
Halting Problem
Time Hierarchy

Reductions For Uncomputability: (ppt, Cook, Questions) (3*1.5hrs)
(Knowing that some computational problems are hard, we prove that
others are.)

Reductions
Simple Reductions
Rice's Theorem
Reverse Reduction
Acceptable
The Post Correspondence Problem
Tiling (Impagliazzo)
CFG G Generates I
CFG G Generates Every String
CFG G Generates Some String
CFG L(G)=L(G')
Game of Life
Hilbert's Tenth Problem (Gems)

No Proof System for Number Theory: (ppt)
(Godel proved that there is no mechanical way of proving everything in
mathematics.)

Gödel's Incompleteness Theorem
Halting << Math Truth

NP-completeness: (ppt, pdf, Questions)
(Reductions involve writing an algorithm for one problem from that for
another. NP-Completeness give strong evidence that most search
problems that industry cares about are believed to not have poly-time
algorithms.)

History
Course vs Schedule
Circuit vs Airplane
Circuit vs 3-Colouring
Non-Deterministic Poly-Time
Reductions
K-Clique vs K-Independent Set
12 Steps
Any P <= Sat
3-Col <= 3-Sat
Sat <= 3-Col
More Problems
12 Steps in More Depth
Making Change scan
Embedding points with distortion pdf

Other Possibilities:

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.