Please enable JavaScript.

Coggle requires JavaScript to display documents.

Computational Complexity (Turing Machines (types (Non-Deterministic Turing…

- - - - banks and companies use RSA to protect our information
        
        hacking
- - - - example: P is in NP
  - - - problems that have efficient algorithms to find their solutions
      - "problems solvable by a deterministic Turing machine bounded in time by a polynomial function of the input length" (https://complexityzoo.uwaterloo.ca/Petting_Zoo).
        
        C: 2.5: polynomial functions
      - common algorithms
        
        linear programming
        
        D: 1.9: solutions of systems of linear equations
        
        testing for primality
        
        sorting
    - - common problems
        
        determining if graphs are isomorphic
      - problems for which it is easy to check if any possible solutions are correct
      - problems solvable in polynomial time by a theoretical non-deterministic Turing machine
    - - if all problems in NP can be reduced in polynomial to a problem, then it is NP-complete
      - common problems
        
        Traveling Salesman Problem
        
        determining if a graph has a Hamiltonian Cycle
    - - contains all proofs (including that of P vs. NP)
        
        E: 1.4: proof by mathematical induction
      - problems for which it is easy to check if any possible solutions are incorrect
- - - - developed lambda calculus
        
        A: Topic 6: Calculus