Chapter 8 Art of the impossible Flashcards

(25 cards)

1
Q

What is a tractable problem?

A

A problem solvable by an algorithm with polynomial time complexity.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does intractable mean in computational complexity?

A

Problems where it is impossible to guarantee finding an exact solution in polynomial time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Why are polynomial-time algorithms favored?

A

Because they are closed under addition/multiplication and typically efficient in practice.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the class P?

A

Set of decision problems solvable in polynomial time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the class NP?

A

Set of decision problems where a ‘yes’ answer can be verified in polynomial time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is NP-completeness?

A

A problem is NP-complete if it’s in NP and all other NP problems can be polynomially reduced to it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What does it mean if a problem is NP-hard?

A

It’s at least as hard as the hardest problems in NP, but not necessarily in NP itself.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the SAT problem?

A

Determining if a CNF formula has a satisfying assignment.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Who proved SAT is NP-complete?

A

Stephen Cook.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the clique problem?

A

A subset of vertices such that every pair of vertices in the subset is directly connected by an edge. Given an undirected graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Is the clique problem NP-complete?

A

Yes, it was proven by reduction from SAT. It is NP-Complete if it is in NP (can verify a solution quickly) and it is NP-hard (at least as hard as any problem in NP)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a decision problem?

A

A problem with a yes/no answer.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Why is reduction important?

A

It helps relate problem complexities by transforming one problem into another.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does the P = NP question ask?

A

The P = NP question asks whether every problem for which a solution can be verified in polynomial time can also be solved in polynomial time.(The P = NP question asks whether every problem whose solution can be verified in polynomial time (i.e., in NP) can also be solved in polynomial time (i.e., is in P).)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the importance of NP-complete problems?

A

Solving any NP-complete problem in polynomial time would solve all problems in NP.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the Hamiltonian Circuit Problem (HCP)?

A

Deciding whether a graph contains a tour visiting each vertex exactly once.

17
Q

How can HCP be used in TSP approximation arguments?

A

By constructing a TSP instance from an HCP input to test approximation algorithm limits.

18
Q

Can all problems be approximated efficiently?

A

No, some approximations (like for TSP) are themselves NP-complete.

19
Q

What is an uncomputable problem?

A

A problem for which no algorithm exists to solve it.

20
Q

What is conjunctive normal form (CNF)?

A

A logical formula composed of ANDs of ORs over Boolean variables.

21
Q

What is Reduction

A

Transforming any instance of the first problem into an instance of a second problem so if we solve the second problem we can get a solution for the first. this mapping of I -> I’ takes polynomial time

22
Q

Approximation loss as a multiplicative factor(

A

multiplicative approximation guarantee, which is a common and formal way to define how good an approximate solution is compared to the optimal one.
s* is the optimal solution cost
s is the cost of an approximate solution

We say that the solution s has an approximation factor of r if
s/s* <= r
If r is closer to 1 the better the approximation
The cost of the approimate solution is at most r times worse than the optimal

23
Q

What are phase transitions (link to SAT)?

A

A phase transition in SAT refers to a sudden change in satisfiability as the number of clauses increases relative to variables.
For 3-SAT, this happens around a ratio of
𝑚/𝑛≈4.26
m/n≈4.26, where problems shift from mostly solvable to mostly unsolvable — and also become hardest to solve.

24
Q

Black-box reduction

A

Given some input I to a problem A, transform I into some I’ which is an instance of Problem B.

Choose an algorithm B alg which can solve Problem B with input I’ and returns true/false accordingly.

Reduced Problem A to Problem B if B alg returns true for input I’ if an only if the solution for problem A is true at I, for all values of I (hence if mapping I to I’ takes polynomial time then the reduction takes polynomial time)

25