Complexity - Space

Question 1

Do define the classes SPACE and NSPACE

Answer 1

Question 2

What is the realtionship between the class TIME(f(n)) and the class SPACE(f(n))?

Answer 2

Question 3

Answer 3

The proof is mathimatical from the number of configurations in a TM that runs on f(n) space.

Question 4

Define PSPACE and NPSPACE

Answer 4

Question 5

Answer 5

Question 6

To what memory class does the language SAT belong? What is the idea of the proof?

Answer 6

Question 7

Why is NP contained in PSPACE? (Intuition of the proof)

Answer 7

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.

Question 8

Define PSPACE-HARD / COMPLETE

Answer 8

Question 9

What are sub-linear space complexity classes?

Answer 9

Question 10

Do define the languages L and NL.

Answer 10

Question 11

What languages are in L?

Answer 11

Question 12

What is the language EQ? To what Space complexity class does it belong?

Answer 12

Question 13

Please name languages in PSPACE.

Answer 13

Question 14

Please name languages that are PSPACE-Complete.

Answer 14

Question 15

Please name languages in NL.

Answer 15

Question 16

What languages are in NPSPACE?

Answer 16

Question 17

What are the stages in the proof?

Answer 17

Question 18

Please name languages in L.

Answer 18

Question 19

Name a language in PSPACE

Answer 19

Question 20

Answer 20

Question 21

Answer 21

Question 22

What languages are NL-complete?

Answer 22

Question 23

What is the language PATH?
To what classes does it belong?

Answer 23

In addition, PATH belongs to SPACE((logn)squared).

Question 24

What languages are PSPACE-complete?

Answer 24

Question 25

What is the language TQBF? Where does it belong?

Answer 25

## Footnote An entire TA was dedicated to proving that **TQBF is PSPACE-complete.** it is **The** PSPACE-complete Language.

Question 26

Please define: A languge A is NL-complete

Answer 26

Question 27

Answer 27

Question 28

## Footnote Note that P is in NP is in NP is in PSPACE is equal to NSPACE

Answer 28

Question 29

How much space does it take to count a polynomial number of items (for example - vertices)?

Answer 29

Logarithmic space.

Question 30

What classes are closed under completion?

Answer 30

Time: R, (RE U coRE)c, P and all the space complexity classes.

Question 31

Answer 31

Question 32

What classes are definitely **not** equal to each other?

Answer 32

NL doesn't equal PSPACE. P doesn't equal EXP.

Question 33

Answer 33

Question 34

Answer 34

Question 35

Answer 35

Question 36

Answer 36

Question 37

**if** P where to equal NP: What wold the relationship between NP and coNP be?

Answer 37

Question 38

Based on the reduction in the picture, what does the reduction theorm say about the class of A-NFA?

Answer 38

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.

Question 39

What classes is PATH in?

Answer 39

P, NLC

Question 40

What classes is SAT in?

Answer 40

NPC, PSPACE=NPSPACE

Question 41

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"?

Answer 41

Yes. (And that is how the reduction from IS to CLIQUE works).

Question 42

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?

Answer 42

Question 43

Please define the language: StronglyConn

Answer 43

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.

Question 44

Answer 44

Question 45

Answer 45

Question 46

Show a log-space reduction from PATH to K2.

Answer 46

Question 47

Answer 47

Question 48

## Footnote 2017 Moed A

Answer 48