Complexity - Time Flashcards
Define the classes: P, NP, and EXPTIME
The class P is closed under what operations?
P is closed under all (classic) operations.
Define a polynomial reduction
How could you prove that a language is in P using the polynomial reduction theorem?
What does it mean that a language L is NP-hard)
It means that if you can solve L (in polynomial time) then you could solve every language in NP (in polynomial time).
Define: a language L in NP-Complete.
Define the language K-SAT
What is the Cook-Levin Theorem?
What have mapping reductions to ATM?
For every L in RE there s a mapping reduction to ATM.
NP belongs to what class?
NP belongs to RE (and to coRE and to R).
What is the proof that Atm is NP-Hard?
Note - It is NP-Hard. This doesn’t mean that it is in NP.
Define the language CLIQUE.
To what class does it belong?
How is this proven?
CLIQUE also belongs to NPC
What is the language IS?
To what class does it belong?
Proof by reduction from CLIQUE
What is the language VC?
To what class does it belong?
Proof by reduction from IS.
What is the language DS?
To what class does it belong?
What is the language SubsetSum?
To what class does it belong?
What are the 6 languages related to the notion of Hamiltonian paths?
To what class do they belong?
Please define the class coNP.
Define: A language L is coNP-Hard / coNP-Complete.
Give 2 examples of languages that are coNP-complete.
Name languages in P
Please name NP-complete languages
Name a case in which there is definitely a mapping reduction between two languages.
In what class is SAT-complement?
Why?
SAT-complement is in coNP-complete.
This is because SAT is NPC, and because of the following rule:
If this unknown statement were true, what others would be true?
How could you prove a language is in NP?
By providing a poly-time verifier for the language.
What is the difference between a vertex cover and a dominating set?
Important Question:
The point is, as opposed to what I thought, this problem is easier, not harder, to solve than SAT which is NPC.
Important Question:
Please detail the reduction from SAT that proves this.
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)).
let A be a language in P. When can we make a polynomial reduction to a language B?
Please define the language D-ST-EULPATH.
{(G,s,t) : G is a directed graph and there is a path from s to t.}
The language belongs to P.
Please define the language:
SetCover
Belongs to NPC
Define the Kleen star operation over a language L.
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 ε.
How is the proof built?
https://www.shulamitrachel.co.il/?ref=4009
2017 moed A
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)
NP = coNP
2018 Moed A
2022 Sem B Moed B
What is the time complexity of Atm?
NP Hard
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?
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).
Note you don’t have to make up a language for L1, the theorem says such a language exists.
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).
