Complexity Theory

Question 1

configuration

Answer 1

tbd

Question 2

end configuration

Answer 2

tbd

Question 3

set of all configurations

Answer 3

tbd

Question 4

C = (q,p,w)

Answer 4

tbd

Question 5

initial configuration

Answer 5

tbd

Question 6

computation of M on x

Answer 6

s

Question 7

Turing computable function

Answer 7

s

Question 8

computation time of M on x

Answer 8

s

Question 9

total computable function

Answer 9

s

Question 10

Blum’s speedup theorem

Answer 10

states that it’s not possible wrt any measure to assign/come up with an optimal implementation/computation for every function, but it’s possible to come with optimal implementations for certain functions

Question 11

decidability (definition)

Answer 11

s

NB: recursive = decidable

Question 12

linear speedup theorem

Answer 12

“is achieved by simply using a bigger TM with more states and a bigger alphabet”

Question 13

NTM

Answer 13

s

Question 14

NP vs co-NP

Answer 14

kann nicht beweisen, dass es das gleiche ist, hängt damit zusammen, dass man von der TM nur eine positive Antwort erhält, d.h. eine akzeptierende Berechnung. Dass das Wort in einer Sprache ist, aber nicht, dass das Wort nicht in einer Sprache ist, dafür gibt es keine akzeptierende Berechnung (NP not closed under complement)

Question 15

Zusammenhang DTIME und NTIME

Answer 15

jede det. Machine kann ich verstehen als nicht-det. Machine, daher DTIME a subset of NTIME

Question 16

Grund, warum P und NP wahrscheinlich nicht gleich sind

Answer 16

P closed under complement, NP not closed under complement

Question 17

essence of a problem in NP

Answer 17

I can guess a justification/a certificate for a positive solution; validate a certificate in polynomial time

Question 18

CLIQUE

Answer 18

CLIQUE asks: “is there a complete subgraph of size m?”

the vertices in the clique tell you how to set the variables so that the boolean formula can be satisfied

Question 19

P-complete

Answer 19

if it is in P and every problem in P can be reduced to it by an appropriate reduction

Question 20

coSAT,

Answer 20

the language of unsatisfiable CNFs, is coNP-complete

Question 21

acceptor TM

Answer 21

s

Question 22

linear speed up theorem

Answer 22

we do not specify how many states our TMs can have so we can speedup a computation always by a linear factor by choosing a TM that has much more states

Question 23

DTIME

Answer 23

s