# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# ## P Problems
# Can be solved
# - Fourier Transforms
# - Searching
# - Sorting
# - Matrix Operations
# - Shortest Path
#
# ## NP Problems
# Can't be solved
# - Prime Factoring
# - Longest Path
# - Boolean Satisfiability
# - Halting Problem
# - Hamiltonian Cycle
#
#
# ## Some Problems
#
# **Fourier Transform** was slow, but became fast with better hardware
#
# **Traveling Salesman Porblem** no fast solution found
#
# |Slow|?|Fast
# |-|-|-|
# |chess|travelling<br/>salesman|multiplication|
# |||sorting|
#
# ## P Problems
# Can be performed in a reasonable amount of time
# - Polynomial time 
# - $S = f(N), S = \Sigma N^{x_i}$, where N is the measure of size of the input, and x is a postive integer
# - Proof that it is fast to do, therefore it is fast to check
#
# ### P Examples
# - Mulitplication
# - Sorting
#
# ## NP Problems
# Answer can be checked within a reasonable amount of time
# - Non-Deterministic Polynomial Time
# - i.e. Polynomial Time to check the correct answer
# - No proof that it can be performed fast
# - P is a subset of NP
#
# ### NP Examples
# - Circuit Design (SAT)
# - Vehicle Routing
# - Job Scheduling
# - Finding primes
# - DB Porblems - feedback vertex set
#
# ### Core NP-Complete Difficulty
# (Categories of related NP problems)
# - Satisfiability
# - Hitting Set
# - Job Sequencing
# - Clique
# - Vertex Cover
# - 3SAT
# - Max Cut
# - Steiner Tree
# - Set Packing
# - Feedback Node Set
# - Feedback Arc Set
# - 0-1 Integer PRogramming
# - Graph Coloring Problem
# - Set Covering
# - 3D Matching
# - Partition
# - Clique Cover
# - Exact Cover
# - Knapsack
# - Directed & Undirected Hamiltonian Circuit
#
# ### EXP Exponential Time
# ### Co-NP
# ### Co-NP Complete
# ### PSpace
# - Exponantial time, but done in a finite amount of space
# ### BPP
# - Can be solved probabilisticly in Polynomial Time
# ### BQP
# - Can eb solved quantum probabilistically in Polynomial Time
#
# ### Others
# - NP Hard
# - RP
# - Co-RP
# - ZPP
# - NC
# - L
# - Exp-Space
# - 2-Exp
# - Decidable
# - Unsolvable
#      - halting problem
#      



StarcoderdataJupyterScriptsDedupFiltered