exponential or factorial number of combinations to check. Travelling salesman problem is in NP. Nobody has managed to prove (yet) that there are no polynomial 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
•Selgub, et iga täpselt formuleeritud probleemi jaoks ei leidugi lahendavat algoritmi! •Vähe sellest: kui võtta “juhuslik” probleem, siis 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
annaabi.ee 
