Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Huji 67521 Computability > Complexity - Space > Flashcards

Complexity - Space Flashcards

1
Q

Do define the classes SPACE and NSPACE

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

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

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

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

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

Define PSPACE and NPSPACE

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

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

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

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

A

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.

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

Define PSPACE-HARD / COMPLETE

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

What are sub-linear space complexity classes?

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

Do define the languages L and NL.

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

What languages are in L?

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

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

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

Please name languages in PSPACE.

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

Please name languages that are PSPACE-Complete.

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

Please name languages in NL.

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

What languages are in NPSPACE?

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

What are the stages in the proof?

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

Please name languages in L.

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

Name a language in PSPACE

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

What languages are NL-complete?

A
23
Q

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

A

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

24
Q

What languages are PSPACE-complete?

A
25
Q

What is the language TQBF? Where does it belong?

A

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

26
Q

Please define: A languge A is NL-complete

A
27
Q
A
28
Q

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

A
29
Q

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

A

Logarithmic space.

30
Q

What classes are closed under completion?

A

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

31
Q
A
32
Q

What classes are definitely not equal to each other?

A

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

33
Q
A
34
Q
A
35
Q
A
36
Q
A
37
Q

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

A
38
Q

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

A

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.

39
Q

What classes is PATH in?

A

P, NLC

40
Q

What classes is SAT in?

A

NPC, PSPACE=NPSPACE

41
Q

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

A

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

42
Q

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?

A
43
Q

Please define the language:
StronglyConn

A

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.

44
Q
A
45
Q
A
46
Q

Show a log-space reduction from PATH to K2.

A
47
Q
A
48
Q

2017 Moed A

A

Huji 67521 Computability (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions