Dla \(\Re(s) > 1\) funkcja dzeta przedstawia się wzorem:
$$\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s}$$
Funkcja ta daje się jednoznacznie przedłużyć analitycznie na całą płaszczyznę zespoloną nie licząc punktu s = 1, gdzie funkcja przechodzi w rozbieżny szereg harmoniczny. Dzeta Riemanna ma tzw. trywialne miejsca zerowe dla s = -2, -4, -6, ... . Hipoteza Riemanna mówi, że wszystkie pozostałe miejsca zerowe znajdują się na prostej \(\Re(s) = \frac{1}{2}\) zwanej prostą krytyczną. G. H. Hardy oraz J. E. Littlewood udowodnili, że jest ich tam nieskończenie wiele. Zostało również udowodnione, że przynajmniej 40% miejsc zerowych leży na prostej krytycznej (Conrey 1989).
Matma
czwartek, 19 stycznia 2012
Problem NP
Problemy milenijne jest to zestaw siedmiu zagadnień matematycznych ogłoszonych przez Instytut Matematyczny Claya 24 maja 2000 roku; za rozwiązanie każdego z nich wyznaczono milion dolarów nagrody. Do dziś rozwiązano tylko jeden problem: hipoteza Poincarégo została potwierdzona w 2006 roku przez rosyjskiego matematyka Grigorija Perelmana.
Osobiście najciekawszym problemem jest dla mnie problem pierwszy:
Problem NP (niedeterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.
Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność.
Przykładowo rozważmy problem:
Problem jest nierozwiązany. Wielokrotnie przedstawiano próby jej udowodnienia jak i obalenia, a także wykazania niedowodliwości.
Osobiście najciekawszym problemem jest dla mnie problem pierwszy:
Problem NP (niedeterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.
Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność.
Przykładowo rozważmy problem:
- Czy jakikolwiek niepusty podzbiór zadanego zbioru (np. {-2,6,-3,72,10,-11}) sumuje się do zera ?
Problem jest nierozwiązany. Wielokrotnie przedstawiano próby jej udowodnienia jak i obalenia, a także wykazania niedowodliwości.
Subskrybuj:
Posty (Atom)