Dacă am găsit un algoritm determinist și polinomial pentru a rezolva problema q-sume (subset sum), care dintre următoarele afirmații este adevărată?

Fie problema q-sume (subset sum) modificată astfel încât vectorul de la intrare conține doar numerele -1 sau +1. (notăm problema unary-q-sume):

Fie o problemă A ∈ NSPACE(f(n)), ∀ f(n)∈Ω(log n). Care din următoarele afirmații este adevărată:

Fie o structură de date pentru care se execută o secvență de n operații cu următoarele costuri: dacă i==2**k, costul operației este 10*i; altfel, costul este 1. Care este complexitatea amortizată per operație?

Fie o structură de date pentru care se execută o secvență de n operații cu următoarele costuri: dacă i este par, costul operației este 1; dacă i este impar, costul este i/10. Care este complexitatea amortizată per operație?

Fie problema q-sume unde q=2 și este fixat (o notăm problema 2-sume). Care dintre următoarele afirmații este adevărată?

Dacă o problemă este în clasa de complexitate PSPACE, atunci ea este sigur și în clasa:

În ce clasă de probleme se află 2-SAT (SAT cu 2 literali per termen)? Alegeți varianta cea mai restrictivă.

Știind că HALT ≤_T A (HALT = problema opririi), ce putem spune sigur despre problema A?

Putem găsi o reducere de la problema corespondențelor lui Po­st (PCP) la SAT?

Fie f(n) ∈θ(n**3) și g(n)∈Ω(n**2), atunci:

Problema determinării dacă două vârfuri dintr-un graf orientat fac parte din aceeași componentă tare conexă este (alegeți clasa de complexitate cea mai restrictivă):

Care este complexitatea amortizată pentru o operație de inserție într-un tabel (vector) dinamic care își dublează spațiul atunci când este plin:

Știm că A ≤_T B, F:I_A → I_B funcția de transformare a a datelor de intrare, iar I_A este mulțimea vectorilor. Dacă în cadrul funcției F operația cea mai costisitoare este construirea tuturor tuplurilor de k (k-fixat, de ex. k=3) elemente din v[1..n] ∈ I_A, este aceasta o reducere polinomială corectă?

Problema determinării dacă un program P, primind la intrare x, se termină în mai puțin de un an este:

Dacă o problemă este în clasa de complexitate NTIME(f(n)), atunci ea este sigur și în clasa:

Care este complexitatea algoritmului de sortare rapidă (quicksort) în cazul cel mai defavorabil, dacă nu se folosește alegerea aleatoare a pivotului:

Știind că A ≤_P SAT, ce putem spune sigur despre problema A:

Pentru ce problemă se știe că dacă există un algoritm de aproximare cu factorul de aproximare < 4/3, atunci P=NP ?

Pentru problema găsirii acoperirii optime cu noduri a unui graf a fost prezentat la curs un algoritm de aproximare cu un factor de:

Care din mulțimile de mai jos sunt bine ordonate față de relația „mai mic”?

Construcția spațiului stărilor pentru un algoritm nedeterminist care are complexitate spațială O(f(n)), are o complexitate temporală de (observație: k este un număr natural):

Complexitatea temporală a problemei accesibilității într-un graf (GAP), rezolvată determinist este:

O problemă P aparține clasei NP-Complete iar o problemă Q clasei NP-Hard. Care afirmație este întotdeauna corectă?

LOGSPACE și PTIME sunt în relația de:

Care din mulțimile de mai jos sunt bine ordonate față de relația „mai mic”?

Construcția spațiului stărilor pentru un algoritm nedeterminist care are complexitate spațială O(f(n)), are o complexitate temporală de (observație: k este un număr natural):

Complexitatea spațială a problemei accesibilității într-un graf (GAP), rezolvată determinist este:

Construirea unui heap binar se poate face optim în:

Dacă găsim o soluție deterministă și polinomială pentru o problemă considerată până acum în NP\P, atunci putem spune că:

Dacă o problemă este în clasa de complexitate NSPACE(n), atunci ea este sigur și în clasa:

Fie o problemă A și știm că PCP ≤ T A (PCP = Problema corespondențelor lui Post). Atunci A este sigur:

Orice algoritm de sortare prin comparație de chei are complexitatea:

O problemă P dată este şi în NPTIME şi NP-completă este o afirmaţie care este:

Care problemă din cele următoare are sigur o complexitate exponenţială:

Problema gasirii unui subgraf de acoperire minim k-arc conectat poate fi rezolvată de algoritmul Khuller-Vîșkin cu un factor de aproximare mai mic de:

GAP aparține mulțimii:

Problema accesibilitatii într-un graf(GAP) rezolvată cu un algoritm determinist are complexitatea spatiala:

Fie A în NSPACE(f(n)) f(n) în omega((log(n))

Mulțimea {n în N| Pn(n) se termina}

Factorul de aproximare pt Viskin pt un graf arc conectivitate:

Problema turnurilor din Hanoi are aceeași complexitate cu:

Mulțimea tuturor programelor are același cardinal cu:

O mulțime finita este întotdeauna:

Ce algoritm are complexitatea Omega(nlog)

Ce teorema justifica imposibilitatea demonstrarea corectitudinii totale a algoritmului?

Problema GAP, rezolvată cu un algoritm nedeterminist se poate face optim cu o complexitate spatiala:

Demonstrarea corectitudinii totale a unui algoritm particular dat este:

Demonstrarea automata a teoremelor de calcul cu predicate de ordinul 1 este o problemă:

Complexitatea amortizata a unei operatii de push într-o stiva cu pop multiplu este:

Problema K-clicii este sigur în aceeași clasa de complexitate cu:

O problema data este semidecidabila și cu o complexitate polinomiala este o afirmatie:

Problema accesibilitatii într-un graf are complexitate temporala:

Prin sortarea proceselor după durata lor în problema alocarii lor pe procesor se poate obtine o rezolvare cu un factor de aproximare mai bun de:

La care dintre urmatoarele probleme s-ar putea găsi un algoritm cu complexitate polinomiala

GAP are o complexitate spatiala:

O mulțime recursiva este întotdeauna:

Multimea problemelor rezolvabile prin algoritmi deterministi cu o complexitate spatiala polinomiala și cea a celor rezolvabile prin algoritmi nedeterministi cu o complexitate spatiala sunt în relație:

Daca exista o problemă Q care este NP-dificila și care aparține PTIME rezulta ca:

PSPACE si NPSPACE sunt în relația:

Daca găsim o soluție determinista și polinomiala pentru o problemă considerată pana acump în NP-P, atunci putem spune ca:

Daca o problemă este în NSPACE(n) atunci ea este sigur și în:

Fie o problemă A și știm ca PCP<t A atunci A este sigur:

Construirea unei cozi de prioritati cu maxim în vârf se face eficient printr-un algoritm:

PSPACE SI NPTIME sunt în relația:

PSPACE SI PTIME sunt în relația:

Care problema dintre urmatoarele este posibil sa aibă o complexitate polinomiala:

Daca o mulțime și complementara ei sunt recursiv enumerabile ea este:

O problema P data este și decidabila și tractabila este o afirmatie:

Consideram ca avem un vector cu operatiile de adaugare si stergere la final, care isi dubleaza capacitatea atunci cand devine plin si si-o injumatateste atunci cand ramane cu mai putin de jumatate din vector ocupat. Care este complexitatea amortizata a operatiilor add si remove, considerand ca n reprezinta numarul curent de elemente din vector?

Fie A o multime recursiva (R), si B o multime recursiv enumerabila (RE), dar nerecursiva. Atunci putem afirma cu siguranta:

Dr. Who anunta ca a descoperit un algoritm nedeter-

minist care rezolva o problema Q in timp polinomial.

Ce afirmatie este adevarata:

Care este complexitatea functiei choice(A)?

Presupunand ca ati gasit o reducere polinomiala de la

3-COLOR la 2-COLOR. Care variante sunt adevarate?