Lehet-e a P, NP osztályoknak kiterjesztése az, amikor a nemdeterminisztikusságban megengedjük a folytonos elágazásokat?

Nem az első hozzászóló vagyok, de én leírom miért gondolom úgy, hogy igaza van.

A teljesség igénye nélkül P és NP osztály:

A P osztály azon számítási feladatok összessége mely polinom időben kiszámítható a feladat méretének függvényében. Azaz a feladat nagyságának polinomjával arányos a számítási időigénye. Azaz például ha n a méret akkor például (O azaz ordó mint ) O(n), O(n^2), O(n^3) időben kiszámítható.

Ilyen például általános esetében két szám összegét kiszámolni ami O(n) idejű. A szorzás már O(n^2) idejű.

Ha NP osztályba tarozik akkor ennek számítási ideje a feladat méretének valamennyi polinomjánál gyorsabban nő az időigénye. Azaz ha veszünk, egy polinomját az lehet hogy gyorsabban fog nőni egy bizonyos tartományon belül nézve, de egy feladat méret felett le fog maradni az a polinomfüggvény.

Az N az determinisztikus polinom idejű, az NP az nemdeterminisztikus polinom idejű. Bonyolultságelméleti szempontból determinisztikus polinom idejű Turing-gépnek mondjuk ami kiszámol valamit determinisztikusan polinom időben, azaz úgymond nincs elágazás ahogy fogalmazol. A nemdeterminisztikus Turing-gép pedig NP osztály beli problémát old meg polinom időben, azaz van elágazás ahogy fogalmazol. Azaz egyszerre veszi az elágazásokat így elméletben, és polinom időben kiszámolja. Viszont sokkal jobb erre inkább úgy tekinteni, hogy bármely konkrét elágazást polinom időben el tud dönteni. Például az RSA titkosítás mely egy lehetséges alkalmazása a TLS biztonsági protokollnak, annak a prímfaktorizáció nehézsége ami NP nehéz feladat adja a biztonságot. Vagyis jól megválsztott két nagy prímszám szorzatát NP nehéz feladat visszafejteni hogy mely két prím ossza. Viszont két konkrét számról eldöteni hogy az e a szorzat eredménye vagy nem már csak P nehéz, valamint az is P nehéz hogy egy konkrét szám ossza e és az prím e.

Kiszámításelméleti szempontból nincs különbség a két fajta Turing gép között, amit egyikkel ki lehet számolni azt ki lehet a másikkal is. Minden esetben véges nagy imputra véges sok esetre véges idő alatt lehet kiszámolni. Ahol véges sok a rendelkezésre álló memória. Pontosabban mondva potenciális végtelen és nem aktuális végtelen. Azaz véges, de tetszőlegesen nagy véges mennyiség az időigény, a memória igény és az input outpout mérete is.

Ezzel szemben, ha az a bizonyos elágazás ha folytonos lenne, az nem hogy aktuális végtelen lenne, hanem nagyobb lenne mint alef-0 végtelen, kontinuum számosság lenne ami még durvább végtelen. Ez itt viszont már ellentmondásba ütközik a kontinuumhipotézissel. Amiről tudjuk, hogy matematikailag bizonyított az, hogy nem bizonyítható és nem is cáfolható. Azaz egy ilyen kiterjesztett Turing-gép konkrét példát tudna adni olyan halmazra amire tudjuk, hogy bizonyítottan elvileg sem lehet rá páldát adni melynek számossága alef-0 és alef-1 között van. Vagy pedig az elágazásokkal nyers erővel végig pörgetné, hogy nincs ilyen halmaz. Ami viszont ellentmondásban van azon axióma rendszerekkel melyekben konkrétan igaz és azokkal melyekben konkrétan hamis a kontinuumhipotézis. Mivel mindkét eset konzisztens és egymástól független matematikai világokban létezik.

Nem szóltatok az elírásra, most nézem ahogy új hozzászólás érkezett:

"Az N az determinisztikus polinom idejű"

Arra gondoltam hogy a P az determinisztikus polinom idejű.

Továbbá kis kiegészítő magyarázat az NP osztály magában foglalja a P osztályt is, NP alatt ennek az NP osztálynak azon részét értettem mely nem P. Feltéve a P nem egyenlő NP sejtést hogy igaz. Amit igaznak gondolnak a matematikusok.