Computational Complexity Theory

• Computational complexity theory is a branch of theoretical computer science that classifies computational problems based on required resources like time and space
• It explores problems' difficulty and the efficiency of algorithms.
• Essentially, this field analyzes programs and their efficiency in a quantified manner.
• There is a focus on quantifying computational resources needed for tasks.

Key Aspects of Computational Complexity Theory

• Complexity classes categorize problems based on resource needs.
• Class P: Problems solvable in polynomial time.
• Class NP: Problems with solutions verifiable in polynomial time.
• Time complexity measures algorithm time as a function of input size.
• Time complexity depends on hardware, varying between a supercomputer and a laptop.

Complexity in Time and Space

• Sample code is shown for illustration

• The size of each variable : 2 Bytes.

• The examples used three variables (i, a, result), which equals 6 Bytes.

• Different execution times are shown depending on whether the sample code is more complex or less complex

• Space complexity measures memory use relative to input size.

P vs NP Problem

• Asks if every problem with quickly verifiable solutions can also be quickly solved.

Reductions

• These are techniques showing one problem being at least as hard as another.
• Helps in understanding limits of computation and guides efficient algorithm development.
• Solvable problems have an algorithm that produces correct output in a finite time for any input.
• Unsolvable problems lack an algorithm to solve them in a finite time.
• The Halting problem asking if a program halts or runs forever is an example of an unsolvable problem.

Problems in Computation Complexity

• Decidable problems have an algorithm determining "yes" or "no" instances in finite time, always halting with the correct answer
• Determining if a number is prime is a decidable
• Undecidable problems lack an algorithm to determine "yes" or "no" instances in finite time.
• The Halting problem, determining if a program halts, is a classic undecidable problem.

P and NP Problems in Computation Complexity

• P problems are solvable in polynomial time.
• NP problems are verifiable in polynomial time.
• The traveling salesman problem along with many other problems are in NP.
• If P = NP, many important computational problems would be efficiently solvable.
• If P != NP, many computational problems may remain fundamentally intractable, limiting automated decision-making.

Space Complexity Classes

• L (Logarithmic Space): Problems solvable with logarithmic memory. Example: path existence in a graph.
• PSPACE (Polynomial Space): Problems solvable with polynomial memory.
• NL (Nondeterministic Logarithmic Space): Problems solvable with logarithmic memory on a nondeterministic Turing machine.
• NPSPACE (Nondeterministic Polynomial Space): Problems solvable with polynomial memory on a nondeterministic Turing machine.
• EXPSPACE (Exponential Space): Problems needing exponential space to solve.
• Complexity encompasses interrelated theories for understanding complex systems.

Chaos Theory

• Examines dynamical systems sensitive to initial conditions ("butterfly effect").
• Small changes can lead to vastly different outcomes, hindering long-term prediction.

Fractal Theory

• Focuses on self-similar patterns across scales.
• Fractals are structures that appear similar at any magnification, like coastlines or bacterial growth.

Catastrophe Theory

• Analyzes how small changes cause sudden shifts in system behavior, such as traffic jams.
• Systems can abruptly change state due to parameter changes.

Complex Adaptive Systems (CAS)

• Are systems that adapt and evolve to environmental changes.
• They consist of interacting agents following simple rules, leading to emergent behavior.

Network Theory

• This studies how element connections affect system behavior.
• Networks exhibit robustness, resilience, and vulnerability based on topology.

Game Theory

• Analyzes strategic interactions where participant outcomes depend on others' actions.
• It's used to model competitive and cooperative behaviors in economics, biology, and social sciences.

Systems Theory

• Is an interdisciplinary study of interconnected systems within larger, complex systems.
• It emphasizes interdependence and interactions between system components.

Nonlinear Dynamics

• This studies systems where output change isn't proportional to input change.
• Nonlinear systems show complex behaviors like chaos and bifurcations.

Turing Machine

• A Turing machine is a hypothetical machine created mathematically by Alan Turning in 1936.
• It is simple, but can simulate any computer algorithm.
• It consists of a head, state register, and infinite length tape divided into cells
• The head reads the input tape.
• The state register stores the Turing machine's state.
• The input symbol is written to the tape is replaced, its internal state is changed, and it moves from one cell to the right or left.
• Input string is accepted if the Turing Machine reaches the final state, otherwise rejected.

Turing Machine Formal Description

• Represented a 7-tuple (Q, X, ∑, δ, q0, B, F).
  • Q is the finite set of states
  • X is the tape alphabet
  • Σ is the input alphabet
  • δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
  • q0 is the initial state
  • B is the blank symbol
  • F is the set of final states
• The Turing machine can perform complex calculations of any duration.
• It simulates computation without predefined resource limits.
• It has an infinitely long tape with blank squares for symbol writing which acts as memory.
• A head positioned over the squares, can process symbols 0 and 1 and blank, making it a 3-symbol machine.

Turing Machine Head Basic operations

• Read the symbol under the head.
• Edit the symbol by writing or erasing it.
• Move the tape left or right to read and edit neighboring symbols.

Turing Machine Rules

• The behavior of the machine is based on its current state and the symbol it reads from the tape.
• Fundamental operations include:
  • Reading the symbol
  • Writing a new symbol
  • Moving the tape head
  • Changing State
• The transition function format is as follows: (Current State, Current Symbol) -> (New State, New Symbol, Direction)

Universal Turing Machine (UTM)

• A theoretical device simulating any other Turing machine.
• Operation:
  • Encoding: UTM takes a description of a Turing machine (M) and an input string (w).
  • Simulation: Reads the encoded description of M and the input string w,, and follows the behavior of M on the input w,.
  • Computation: Follow the rules of M, reading symbols from the tape, writing new symbols.
  • Output: Produces the same output of M on a given input w
• Demonstrates that a single machine can perform any computation of another Turing machine.
• A modern basis is based on a universal machine.
• Understanding computation limits: The UTM helps understand computation limits, such as the unsolvable Halting Problem.

Non-Deterministic Turing Machines (NDTMs)

• A theoretical computation model extending deterministic Turing machines.
• NDTMs can have multiple possible actions for each configuration
• Deterministic Turing Machine: One possible next move
• Non-Deterministic Turing Machine: Multiple possible next moves

NDTM - Operation

• Multiple Paths: NDTM can "guess" the correct move, leading to multiple computation paths.
• Acceptance: The NDTM accepts an input if any computation path leads to an accepting state.

Computability of Turing Machines

• You can simulate a program by using a Turing machine.
• Standard algorithms (addition/multiplication) can be expressed as Turing machines.
• Most programming languages can simulate a Turing machine.

Quantum Computers

• New computation model with exponential advantages over classical models (probabilistic, deterministic Turing machines).
• Challenges the Church-Turing thesis due to simulating computation with polynomial overhead.
• There is a polynomial-time algorithm for quantum computers to factor integers. Which exceeds current deterministic and probabilistic processes in terms of efficiency.

Church-Turing Thesis

• This is a nature hypothesis about computable functions.
• Function on natural numbers can be calculated with Turing Machine.
• Named it the Alonzo Church and Alan Turing
• Turing's machines manipulate strings with tape, while Church made a mechanical method 'M' for string manipulation using logic and mathematics.