Complexity - Time

Question 1

Define the classes: P, NP, and EXPTIME

Answer 1

Question 2

Answer 2

Question 3

The class P is closed under what operations?

Answer 3

P is closed under all (classic) operations.

Question 4

Define a polynomial reduction

Answer 4

Question 5

How could you prove that a language is in P using the polynomial reduction theorem?

Answer 5

Question 6

What does it mean that a language L is NP-hard)

Answer 6

It means that if you can solve L (in polynomial time) then you could solve every language in NP (in polynomial time).

Question 7

Define: a language L in NP-Complete.

Answer 7

Question 8

Answer 8

Question 9

Define the language K-SAT

Answer 9

Question 10

What is the Cook-Levin Theorem?

Answer 10

Question 11

What have mapping reductions to ATM?

Answer 11

For every L in RE there s a mapping reduction to ATM.

Question 12

NP belongs to what class?

Answer 12

NP belongs to RE (and to coRE and to R).

Question 13

What is the proof that Atm is NP-Hard?

Answer 13

Note - It is NP-Hard. This doesn’t mean that it is in NP.

Question 14

Define the language CLIQUE.
To what class does it belong?
How is this proven?

Answer 14

CLIQUE also belongs to NPC

Question 15

What is the language IS?
To what class does it belong?

Answer 15

Proof by reduction from CLIQUE

Question 16

What is the language VC?
To what class does it belong?

Answer 16

Proof by reduction from IS.

Question 17

What is the language DS?
To what class does it belong?

Answer 17

Question 18

What is the language SubsetSum?
To what class does it belong?

Answer 18

Question 19

What are the 6 languages related to the notion of Hamiltonian paths?
To what class do they belong?

Answer 19

Question 20

Please define the class coNP.

Answer 20

Question 21

Define: A language L is coNP-Hard / coNP-Complete.

Answer 21

Question 22

Answer 22

Question 23

Give 2 examples of languages that are coNP-complete.

Answer 23

Question 24

Name languages in P

Answer 24

Question 25

Please name NP-complete languages

Answer 25

Question 26

Answer 26

Question 27

Answer 27

Question 28

Answer 28

Question 29

Answer 29

Question 30

Name a case in which there is definitely a **mapping** reduction between two languages.

Answer 30

Question 31

Answer 31

Question 32

Answer 32

Question 33

In what class is SAT-complement? Why?

Answer 33

SAT-complement is in coNP-complete. This is because SAT is NPC, and because of the following rule:

Question 34

If this unknown statement were true, what others would be true?

Answer 34

Question 35

How could you prove a language is in NP?

Answer 35

By providing a poly-time verifier for the language.

Question 36

Answer 36

Question 37

What is the difference between a vertex cover and a dominating set?

Answer 37

Question 38

Important Question:

Answer 38

The point is, as opposed to what I thought, this problem is easier, not harder, to solve than SAT which is NPC.

Question 39

Important Question: Please detail the reduction from SAT that proves this.

Answer 39

Note! 1. One can't just add variables with the values "True" or "False". Instead, one can add new variables of the form xi and not(yi) and assign T to xi and F to yi. 2. in this case they proved the iff part of the reduction by showing: (if A than B) and also (if B than A), (as opposed to the normal way of (if A than B) and also (if not A then not B)).

Question 40

Answer 40

Question 41

let A be a language in P. When can we make a polynomial reduction to a language B?

Answer 41

Question 42

Answer 42

Question 43

Please define the language D-ST-EULPATH.

Answer 43

{(G,s,t) : G is a directed graph and there is a path from s to t.} The language belongs to P.

Question 44

Please define the language: SetCover

Answer 44

Belongs to NPC

Question 45

Define the Kleen star operation over a language L.

Answer 45

The Kleene star operation over L, denoted as L*, is defined as the set of all possible concatenations of zero or more strings from L, including the empty string ε.

Question 46

How is the proof built?

Answer 46

## Footnote https://www.shulamitrachel.co.il/?ref=4009

Question 47

## Footnote 2017 moed A

Answer 47

Note the to make a = b is the same as: a<-> b = (a->b) AND (b->a) = (NOT a OR b) AND (NOT b OR a)

Question 47

Answer 47

NP = coNP

Question 48

## Footnote 2018 Moed A

Answer 48

Question 49

Answer 49

Question 50

## Footnote 2022 Sem B Moed B

Answer 50

Question 51

What is the time complexity of Atm?

Answer 51

NP **Hard**

Question 52

Answer 52

Question 53

How can you build a function f for a reduction that gives a different f(x) based on if a certain TM does or does not accept a certain input?

Answer 53

Note how f returns a TM (M') that runs a different TM (M) and then based on the result of the run - simulates a specific third TM (Mf).

Question 54

Answer 54

Note you don't have to make up a language for L1, the theorem says such a language exists.

Question 54

Answer 54

Note how in this reduction we simply **added** to original graph** exactly what we needed.** (The reduction simply adds a clique of size 2k made of new nodes).