Complexity Theory Flashcards
configuration
tbd
end configuration
tbd
set of all configurations
tbd
C = (q,p,w)
tbd
initial configuration
tbd
computation of M on x
s
Turing computable function
s
computation time of M on x
s
total computable function
s
Blum’s speedup theorem
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
decidability (definition)
s
NB: recursive = decidable
linear speedup theorem
“is achieved by simply using a bigger TM with more states and a bigger alphabet”
NTM
s
NP vs co-NP
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)
Zusammenhang DTIME und NTIME
jede det. Machine kann ich verstehen als nicht-det. Machine, daher DTIME a subset of NTIME
Grund, warum P und NP wahrscheinlich nicht gleich sind
P closed under complement, NP not closed under complement
essence of a problem in NP
I can guess a justification/a certificate for a positive solution; validate a certificate in polynomial time
CLIQUE
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
P-complete
if it is in P and every problem in P can be reduced to it by an appropriate reduction
coSAT,
the language of unsatisfiable CNFs, is coNP-complete
acceptor TM
s
linear speed up theorem
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
DTIME
s
