Week 2 -P vs NP

Question 1

Given 2 functions f(n) and g(n)
define big o

Answer 1

f(n) = O(g(n)) if there exists some c ( where c>0 ) such that for all values of n f(n)<= c x g(n) where n>= n0 (n0 >=0)

Question 2

define big omega

Answer 2

f(n) = Ω(g(n)) if there exists some c ( where c>0 ) such that for all values of n f(n)>= c x g(n) where n>= n0 (n0 >=0)

Question 3

define big theta

Answer 3

f(n) =O(g(n)) AND Ω(g(n))

Question 4

What is the language of a decision problem

Answer 4

Every problem for which the answers are yes or No can be a language

Lp = w ∈ Σ* : w is an instance of problem P whose answer is yes

Question 5

Time complexity tM(w) of a deterministic machine ( given a terminating machine)

M is a subscript character

Answer 5

number of steps required to terminate on an input word w ∈ Σ*

Question 6

Time complexity tM(w) of a non-deterministic machine ( given a terminating machine)
M is a subscript character

Answer 6

the number of steps in the single longest computation of the input w be it one that terminates in an accepting or rejecting state

Question 7

Worst case time complexity (Tm(n)) - m is a subscript character

Answer 7

max {t(w) : all words w of length n}

looks at every possible input of length n and identifies longest to process

Question 8

P (Polynomial Time): This refers to the class of problems that can be solved efficiently by a computer, meaning that an algorithm exists that can find the solution in a time that grows at a polynomial rate with the size of the input. In simpler terms, if a problem is in P, it means there is a known fast solution to it.

NP (Nondeterministic Polynomial Time): This refers to the class of problems for which a given solution can be verified efficiently, even if we don’t know how to find that solution quickly. If a problem is in NP, it means that while it might be hard to solve, if someone gave you a solution, you could check it quickly.

The Big Question: P vs NP
P problems are “easy to solve.”
NP problems are “easy to verify.”

Answer 8

asdgiash

Question 9

P what it is

Answer 9

(Deterministic) polynomial time
A langauge L is said to be solvable in polynomial time if there exists
a deterministic Turing Machine M such that:
. M accepts L
. Polynomial time complexity O(n^k) dont get confused with exponential

P is the class of all languages solvable in Deterministic polynomial time

Question 10

NP what is it

Answer 10

Non-Deterministic polynomial time
A langauge L is said to be solvable in non-deterministic polynomial time if there exists
a non-deterministic Turing Machine M such that:
. M accepts L
. Polynomial time complexity O(n^k) dont get confused with exponential

NP is the class of all languages solvable in Non-Deterministic polynomial time

Question 11

what is NP Complete

Answer 11

. Np hard
.in NP

Question 12

Examples of NP complete problems

Answer 12

Boolean satisfiability problem
Clique Problem
Hamiltonian Cycle Problem
Travelling Salesman Problem
Graph Colouring Problem
Knapsack Problem