NP complete 1-18

Question 1

Given a graph G=(V,E), find the chromatic number.
what type of proplem is that

Answer 1

Optimization problem

Question 2

what is Chromatic number problem………

Answer 2

smallest number of colors needed to color a graph

Question 3

what type of proplem is this :Given a graph G=(V,E) and an integer k, is G k-colorable?

Answer 3

decicion proplem

Question 4

T or F:solving general problem is as hard as solving the decision problem version.

Answer 4

T

Question 5

what is intractable proplems

Answer 5

They grow large, we are unable to solve them in reasonable time

Question 6

T or F:Polynomial-Time Algorithm are intractable

Answer 6

F

Question 7

O(1), O(log n) is polynmial time algorthim

Answer 7

T

Question 8

The class P consists of….

Answer 8

all those problems that are solvable in polynomial time

Question 9

Examples of P proplems

Answer 9

Sorting; merge sort, heapsort, insertion sort, etc.
Searching; linear or binary
Matrix multiplications
Single-source shortest path problem; Bellman-ford and Dijkstra algorithms

Question 10

proplems that require exponential time 2ˆn to solve

Answer 10

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

Question 11

diffrence in defntions between P and NP proplems

Answer 11

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.

Question 12

NP stands for …….

Answer 12

nondeterministic polynomial

Question 13

NP is the class of decision problems that
 are solvable in polynomial time with a ………… algorithm.

Answer 13

nondeterministic

Question 14

Non-deterministic algorithm

Answer 14

Example-Search problem:
Check if X found in a set (1:n)?

Question 15

p is ………. and……..
NP is …………. but…..

Answer 15

p easy to solve and easy to check
np is hrad to solve but easy to check

Question 16

Open question since 1970

Answer 16

Is P = NP ?

Question 17

complete what written under this digram

Answer 17

Question 18

when dose problems becomes NP-complete (NPC)

Answer 18

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.

Question 19

give examples of NP-complete proplems

Answer 19

3-SAT problem, Hamiltonian cycle problem, longest path problem, etc.

Question 20

A decision problem Q is NP-complete if:

Answer 20

Q ∈ NP
for all R ∈ NP, R ≤pQ

Question 21

How to Prove a Problem L is NP-Complete?

Answer 21

Question 22

NP-Hard problems

Answer 22

At least as hard as the hardest problems inNP.

Question 23

If all problems in NP are polynomial-time reducible to Q, then Q is …..

Answer 23

NP-Hard

Question 24

T or F: NP-Hard ∈ NP.

Answer 24

not neccarly

Question 25

Theorems proveing np-hard

Answer 25

If R≤pQ and R is NP-Hard, Q is also NP-Hard.

Question 26

NP-Hard and NP-complete problems in theory

Answer 26

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.

Question 27

talk about a property in NP-complete

Answer 27

If any one NP-complete problem can be solved in polynomial time, then every problem in NP can also be solved similarly

Question 28

list three 2ˆn algorthims

Answer 28