PR�B�H P�EDN��KY V�PO�TOV� SLO�ITOST (ZIMN� SEMESTR 2007/2008)

==========================  9.10.2007  ==============================

Budeme se zab�vat t�m, jak velk� prostor a �as je pot�ebn� k �e�en� �loh na po��ta�i.
Algoritmicky ne�e�iteln� �lohy:
 - L(G) = \Sigma^*
 - L(G_1) \cap L(G_2) \not= 0
 - probl�m slov v obecn� asociativn� algeb�e
 - polynomi�ln� rovnice v�ce prom�nn�ch v p�irozen�ch ��slech 
   (d�kaz ne�e�itelnosti poch�z� od Matijasevi�e, 10. Hilb. probl�m)
P��klady n�ro�n�ch �loh:
 - probl�m obchodn�ho cestuj�c�ho (TSP)
 - kone�n� hry (�achy, go, hra na grafech)
 - probl�m splnitelnosti v�rokov�ch formul� (SAT)
Algoritmus n�soben� n bitov�ch ��sel slo�itosti n^log_2 3.
Existuje algoritmus slo�itosti O(n log n log log n).
P�ipomenuto zna�en� O(f), \Omega(f).

==========================  16.10.2007  ==============================

Algoritmick� ne�e�itelnost polynomi�ln�ch rovnic v cel�ch ��slech.
Polo�ena ot�zka �sporn�j�� parametrizace n p�irozen�ch ��sel pomoc�
cel�ch ��sel ne� pomoc� 4n parametr�.

D�kaz vz�jemn� p�evoditelnosti n�sleduj�c�ch probl�m�
 (A) splnitelnost Booleovsk�ch formul� v KNF 
 (B) �e�itelnost soustav polynomi�ln�ch rovnic v t�lese Z_2.
 (C) splnitelnost obecn�ch Booleovsk�ch formul� v b�zi v�ech bin�rn�ch spojek
P�evod �lohy typu (A) na (B) pomoc� p�episu klausule l_1, ..., l_k
na polynom (1 - (1 - l_1)...(1 - l_k)).
P�evod �lohy typu (B) na (C) lze prov�st n�hradou n�soben� za konjunkci
a s��t�n� za nonekvivalenci.
P�evod �lohy typu (C) na (A) vy�aduje p�id�n� nov�ch prom�nn�ch, kter�
popisuj� hodnoty v�ech podformul�. S pomoc� t�chto nov�ch prom�nn�ch
se vyhodnocen� formule pop��e pomoc� lok�ln�ch podm�nek svazuj�c�ch
ka�dou podformuli s jej�mi bezprost�edn�mi podformulemi.

Shrnuty pojmy
 - rozhodovac� �loha
 - v�po�et funkce
 - vyhled�vac� �loha
Zaveden pojem optimaliza�n� �loha.

==========================  23.10.2007  ==============================

- P��klady optimaliza�n�ch �loh, rozhodovac� varianta, v�po�et optima,
  hled�n� optim�ln�ho �e�en�.
- Zaveden� TS s jednou a v�ce p�skami, kop�rov�n� s jednou a dv�ma p�skami.
- Zna�en� pro �as t(w), t(n) a prostor s(w), s(n) pro konkr�tn� TS. V�po�ty
  s prostorovou slo�itost� men�� ne� n.
- RAM, jednotkov� a logaritmick� (bitov�) slo�itost.
- RAM s n�soben�m. Jednotkov� a bitov� slo�itost n n�sobn�ho umocn�n� na druhou.
- RAM bez n�soben� a d�len�. Slo�itost operace trunc(x/2).
  Pozn�mka: Navr�en� algoritmus pro trunc(x/2) s konstantn�m prostorem
  m� jednotkovou slo�itost O(n^2), kde n je d�lka z�pisu x.
- Po�adavek rozumn�ho k�dov�n�. Mus� b�t efektivn� (nejv��e polynomi�ln�)
  p�evod mezi k�dem a p�vodn� strukturou v modelu, kdy m��eme p��mo pracovat
  s libovoln�mi kombinatorick�mi strukturami. Nen� to exaktn� definovan� pojem,
  proto�e nen� form�ln� zaveden pot�ebn� v�po�etn� model.
  Zm�nka o probl�mu testov�n� a^b \lt c^d pro n bitov� ��sla.

Pozn�mka: V roce 1796 dok�zal Gauss, �e ka�d� p�irozen� ��slo je
sou�tem t�� troj�heln�kov�ch ��sel, co� jsou ��sla tvaru n(n+1)/2,
tedy choose(n+1,2).

==========================  30.10.2007  ==============================

Transformace rovnice n prom�nn�ch z N na 
 1. rovnici s 11 prom�nn�mi ze Z pomoc� zes�len� Matijasevi�ovy v�ty
 2. rovnici s 3n prom�nn�mi ze Z pomoc� Gaussova v�sledku o sou�tu
    t�� troj�heln�kov�ch ��sel.
Hled�n� spl�uj�c�ho ohodnocen� v�rokov� formule pomoc� testu splnitelnosti.
Hled�n� Hamiltonovsk� kru�nice pomoc� testu p��tomnosti takov� kru�nice.
�vaha o hled�n� d�kazu matematick� v�ty pomoc� testu dokazatelnosti.
Pozn�mka, �e algoritmicky nerozhodnuteln� probl�m mus� obsahovat
  instance nez�visl� na teorii mno�in.
Konstrukce jazyka L_f pro danou funkci s polynomi�ln� omezenou
  d�lkou v�stupu. D�kaz, �e L_f je v P pr�v� kdy� f je vy��sliteln�
  v polynomi�ln�m �ase.
Zaveden� t��d DTIME(t) a DSPACE(s).
Blumova v�ta o (exponenci�ln�m) zrychlen�. D�sledek: nelze definovat
  slo�itost �lohy, jen algoritmu. Slo�itost �lohy lze charakterizovat
  jen t�m, zda L pat�� do DTIME(t) nebo DSPACE(s) pro konkr�tn�
  m�ry slo�itosti t,s. Mno�ina takov�ch t,s nemus� m�t minimum.
Zm�nka o v�t� o d�r�ch a o konstruovatelnosti.
Zaveden� Booleovsk�ch obvod�. Transformace polynomi�ln�ho v�po�tu TS
  na polynomi�ln� velk� obvod.
Neuniformn� modely. TS s pomocnou funkc� alpha.

==========================  6.11.2007  ==============================

Algoritmy na RAM bez d�len� a n�soben� pro v�po�et trunc(x/2)
s konstantn� pam�t�.
Zaveden� P/poly, LOGSPACE/poly.
formule \subseteq LOGSPACE/poly (bez d�kazu).
obvody = P/poly (bez d�kazu).
Toto d�v� do souvislosti porovn�n� s�ly v�rokov�ch formul�
a obvod� s porovn�n�m neuniformn�ch variant t��d LOGSPACE a P,
o kter�ch se p�edpokl�d�, �e vno�en� LOGSPACE do P je ostr�.
STCONN je v DSPACE(log^2 n).
USTCONN je v DSPACE(log n) = LOGSPACE.
Pravd�podobnostn� TS.
Polynomi�ln� pravd�podobnostn� TS lze simulovat ve t��d� P/poly.
Ekvivalence read-once rozhodovac�ch diagram� je rozhodnuteln�
pravd�podobnostn�m TS v poly �ase.
(Stroj m��e nezjistit neekvivalenci, ale nem��e ud�lat chybu,
pokud jsou ekvivalentn�.)
Interaktivn� pravd�podobnostn� d�kaz neizomorfnosti dvou graf�.

==========================  13.11.2007  ==============================

LOGSPACE \subseteq P.
Tak� LOGSPACE/poly \subseteq P/poly.
Polynomi�ln� formule pro maticovou funkci "v ka�d�m sloupci dv� jedni�ky po sob�".
Logaritmick� prostor na TS pro tuto �lohu.
Programovac� jazyk pro TS.
Simulace k-p�skoveho 1-p�skov�m TS.
N�znak simulace k-p�skov�ho 2-p�skov�m TS.
Ulo�en� registr� RAM na p�sce TS.

==========================  20.11.2007  ==============================

Simulace RAM pomoc� TS.
Simulace RAM pomoc� efektivn� konstruovateln�ch obvod�.
Ekvivalence P/poly a obecn�ch obvod�.
Zaveden� p-p�evoditelnosti.
SAT je p-p�evediteln� na probl�m klika v grafu.

==========================  27.11.2007  ==============================

p-p�evoditelnost probl�mu kliky na SAT.
Splnitelnost Booleovsk�ch obvod� je NP-�pln� �loha.
Vyj�d�en� lok�ln�ch podm�nek pro spln�n� obvod� d�v� formuli
v KNF, co� dokazuje NP-�plnost SAT.
p-p�evoditelnost SAT na 3-SAT.

==========================  4.12.2007  ==============================

NP-�plnost probl�mu p�esn�ho 3-pokryt�.
Vz�jemn� p-p�evoditelnost probl�mu batohu s p�irozen�mi a s cel�mi ��sly.
NP-�plnost probl�mu batohu s p�irozen�mi ��sly p�evodem z 3-SAT.

==========================  11.12.2007  ==============================

Probl�m batohu s cel�mi ��sly.
Probl�m rozd�len� v p�irozen�ch a cel�ch ��slech.
Ekvivalence v�ech uveden�ch variant probl�mu batohu.
Probl�m batohu lze �e�it v �ase, kter� je polynomi�ln�
v hodnot�ch ��sel n,b.
V�ta o �plnosti rezoluce (zat�m bez d�kazu).
D�sledek: 2-SAT je v P.
Nedokon�en� �e�en� 2-SAT pomoc� grafu.
Zaveden� aproxima�n�ch algoritm�.
Probl�m vrcholov�ho pokryt� a jeho souvislost
s probl�mem kliky (zat�m bez d�kazu).

==========================  18.12.2007  ==============================

Vz�jemn� p-p�eveditelnost probl�mu kliky a vrcholov�ho pokryt�.
Dokon�en� testu 2-SAT p�es tranzitivn� uz�v�r implikac�.
D�kaz �plnosti rezolu�n� metody.
Aproxima�n� algoritmus pro vrcholov� pokryt� s faktorem 2.