Please enable JavaScript.

Coggle requires JavaScript to display documents.

Limits to Compution - Coggle Diagram

- - - - Checking all possible answers in paralell to determine which is correct
    - - NP-Complete: In a non-deterministic computer, you could find the correct answer in polynomial time
      - An NP problem can be NP, NP-hard and also P(olynomial)
    - - Prove that X is in NP (giving a suitable polynomial-time. nondeterministic algorithm)
        
        Prove that X is NP-Hard
        
        "To prove that X is N P-hard, we choose a known NP-complete problem, say A. We describe a polynomial-time transformation that takes an arbitrary instance I of A to an instance I_0 of X. We then describe a polynomial-time transformation from SLN_0 to SLN such that SLN is the solution for I"