NP complete 1-18 Flashcards
Given a graph G=(V,E), find the chromatic number.
what type of proplem is that
Optimization problem
what is Chromatic number problem………
smallest number of colors needed to color a graph
what type of proplem is this :Given a graph G=(V,E) and an integer k, is G k-colorable?
decicion proplem
T or F:solving general problem is as hard as solving the decision problem version.
T
what is intractable proplems
They grow large, we are unable to solve them in reasonable time
T or F:Polynomial-Time Algorithm are intractable
F
O(1), O(log n) is polynmial time algorthim
T
The class P consists of….
all those problems that are solvable in polynomial time
Examples of P proplems
Sorting; merge sort, heapsort, insertion sort, etc.
Searching; linear or binary
Matrix multiplications
Single-source shortest path problem; Bellman-ford and Dijkstra algorithms
proplems that require exponential time 2ˆn to solve
Satisfiability — 2^n
0/1 Knapsack — 2^n
Traveling SP (Traveling Salesman Problem) — 2^n
Sum of Subsets — 2^n
Graph Coloring — 2^n
Hamiltonian Cycle — 2^n
diffrence in defntions between P and NP proplems
The class P consists of all those problems that are solvable in polynomial time.
.
The class NP consists of all those problems that are verifiable in polynomial time.
NP stands for …….
nondeterministic polynomial
NP is the class of decision problems that are solvable in polynomial time with a ………… algorithm.
nondeterministic
Non-deterministic algorithm
Example-Search problem:
Check if X found in a set (1:n)?
p is ………. and……..
NP is …………. but…..
p easy to solve and easy to check
np is hrad to solve but easy to check
Open question since 1970
Is P = NP ?
complete what written under this digram
when dose problems becomes NP-complete (NPC)
A problem is in the class NP-complete (NPC) if it is in NP and is as “hard” as any problem in NP.
The hardest problems in NP.
give examples of NP-complete proplems
3-SAT problem, Hamiltonian cycle problem, longest path problem, etc.
A decision problem Q is NP-complete if:
Q ∈ NP
for all R ∈ NP, R ≤pQ
How to Prove a Problem L is NP-Complete?
NP-Hard problems
At least as hard as the hardest problems inNP.
If all problems in NP are polynomial-time reducible to Q, then Q is …..
NP-Hard
T or F: NP-Hard ∈ NP.
not neccarly
Theorems proveing np-hard
If R≤pQ and R is NP-Hard, Q is also NP-Hard.
NP-Hard and NP-complete problems in theory
If R ≤pQ and R is NP-Complete, then Q is NP-Hard.
If R ≤pQ and R is NP-Complete and Q is NP, then Q is NP-Complete.
talk about a property in NP-complete
If any one NP-complete problem can be solved in polynomial time, then every problem in NP can also be solved similarly
list three 2ˆn algorthims
