Complexity - Space Flashcards
Do define the classes SPACE and NSPACE
What is the realtionship between the class TIME(f(n)) and the class SPACE(f(n))?
The proof is mathimatical from the number of configurations in a TM that runs on f(n) space.
Define PSPACE and NPSPACE
To what memory class does the language SAT belong? What is the idea of the proof?
Why is NP contained in PSPACE? (Intuition of the proof)
Because a language L in NP can be verified in polynomial time. Thus a TM can be built that decides L in polynomial time by running all the possible verifiers (of which there is a finite number). each verification is in polynomial time - and therefore in polynomial space. The TM reuses the same space for testing each verifier.
Define PSPACE-HARD / COMPLETE
What are sub-linear space complexity classes?
Do define the languages L and NL.
What languages are in L?
What is the language EQ? To what Space complexity class does it belong?
Please name languages in PSPACE.
Please name languages that are PSPACE-Complete.
Please name languages in NL.
What languages are in NPSPACE?
What are the stages in the proof?
Please name languages in L.
Name a language in PSPACE
What languages are NL-complete?
What is the language PATH?
To what classes does it belong?
In addition, PATH belongs to SPACE((logn)squared).
What languages are PSPACE-complete?
What is the language TQBF? Where does it belong?
An entire TA was dedicated to proving that TQBF is PSPACE-complete. it is The PSPACE-complete Language.
Please define: A languge A is NL-complete
Note that P is in NP is in NP is in PSPACE is equal to NSPACE
How much space does it take to count a polynomial number of items (for example - vertices)?
Logarithmic space.
What classes are closed under completion?
Time: R, (RE U coRE)c, P
and all the space complexity classes.
What classes are definitely not equal to each other?
NL doesn’t equal PSPACE.
P doesn’t equal EXP.
if P where to equal NP:
What wold the relationship between NP and coNP be?
Based on the reduction in the picture, what does the reduction theorm say about the class of A-NFA?
The reduction theorem won’t say here that A-NFA is also in L because, in order to prove that you would need to show a log space reduction. This is becase the idea of the reduction theorem is that you could use the reduction so you could solve language A by solving language B.
What classes is PATH in?
P, NLC
What classes is SAT in?
NPC, PSPACE=NPSPACE
Could the prossess of going over a graph A and creating a graph B with an edge between every two vertices that do not have an edge between them in A - count as a “reduction”?
Yes.
(And that is how the reduction from IS to CLIQUE works).
To what operations are the following classes closed?
L, NL, coNL, P, NP, coNP, PSPACE, NPSPACE, EXP?
NP-H\C, coNP-H\C, PSPACE-H\C, NPSPACE-H\C?
Please define the language:
StronglyConn
StronglyConn = {(G) s.t G is strongly connected.}
A graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected.
Show a log-space reduction from PATH to K2.
2017 Moed A
