algorithms for P. Open question: does NP = P ? Lahenduvus: Selgub, et iga täpselt formuleeritud probleemi jaoks ei leidugi lahendavat algoritmi! Uuritakse, millistele ülesannetele on algoritme, millistele ei Uuritakse, mis ülesande lahendamine taandub teisele ülesandele Uuritakse lahendumist, poollahendumist, kreatiivseid hulki jne jne Uuritakse lõpmatuse struktuuri, mis on kirjeldamatult keeruline Uuritakse lahendumise struktuuri, mis on kirjeldamatult keeruline Uuritakse loogikaklasside lahendumise taandumist muudele ülesannetele Kuidas lahendamatust näidata (plaan): Näitame, et algoritme on sama palju, kui täisarve (lihtne) Näitame, et probleeme on vähemalt sama palju, kui reaalarve (veidi keerulisem) Näitame, et reaalarve on lõpmatult rohkem kui täisarve (Cantori üks teoreeme) Cantori teoreem ütleb üldisemalt, et mingi hulga H kõigi alamhulkade hulk on suurema võimsusega kui see hulk H. Poollahenduvus
tõenäosus, et lahendav algoritm leidub, on lõpmatult väike! ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 24 Lahenduvuse uurimise sisu .Uuritakse, millistele ülesannetele on algoritme, millistele ei .Uuritakse, mis ülseande lahendamine taandub teisele ülesandele .Uuritakse lahendumis, poollahendumist, kreatiivseid hulki jne jne .Uuritakse lõpmatuse struktuuri, mis on kirjeldamatult keeruline .Uuritakse lahendumise struktuuri, mis on kirjeldamatult keeruline .Uuritakse loogikaklasside lahendumise taandumist muudele ülesannetele ..... ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 25 Intuitiivne selgitus lahendamatusele •Selleks näitame: .Algoritme on sama palju, kui täisarve .Probleeme on sama palju reaalarve .Reaalarve on rohkem kui täisarve ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 26 Kui palju on algoritme? •Iga algoritmi saab realiseerida mingis programmeerimiskeeles –valime näiteks C •Iga C programm on sisuliselt string
annaabi.ee 
