Milyen bonyolultsági osztályba sorolható az a probléma, hogy egy R^n -> R függvény mely változóitól függ?

Megszámlálhatóan végtelen sok (azaz alef-0) algoritmus létezik. Az R^n -> R, ebből már csupán csak maga R halmaz számossága magasabb rendűen végtelen, méghozzá kontinuum végtelen (azaz alef-1). Arról nem is beszélve, hogy az R^n -> R függvények számossága mennyi, még durvább végtelen.

Vagyis általános esetben semmilyen algoritmussal nem írható le az R^n -> R függvény. Ezen függvények csak igen kis részére létezik egyáltalán algoritmus. Így bonyolultsági osztályba nem sorolható. Az meg esetlegesség, hogy azon elenyésző R^n -> R függvények melyekre létezik algoritmus melyik bonyoloultsági osztályba sorolható, de akkor is csak akkor, ha olyan alakba van írva (pl zárt alak, ill. eleve algoritmus van rá írva amit látunk), mert egyébként a végtelen sok bemenetet nem lehet végigpróbálgatni.

#1, szerintem a kérdező úgy érti a kérdést, hogy tetszőleges n esetén megmondható-e egy függvényről, hogy redukálható-e, nem az n->végtelen esetre gondol.

Ez ugyanaz, minthogy léteznek végtelen sok csúcsot tartalmazó gráfok is, mégsem ezekben szoktuk feltenni a kérdést, hogy egy adott gráfról hogyan lehet eldönteni, hogy van-e benne Hamilton-út/kör, és erre az a válasz, hogy nincs válaszunk.

Mivel a függvényeknél 2^n darab esetet kell végigvizsgálnunk, ezért szerintem ez is NP-probléma.

@14:16

"#1, szerintem a kérdező úgy érti a kérdést, hogy tetszőleges n esetén megmondható-e egy függvényről, hogy redukálható-e, nem az n->végtelen esetre gondol."

Én csak arra válaszoltam amit kérdezett, nem arra hogy mit gondol valaki hogy mit gondol a kérdező vagy mit gondolt a kérdező, ha pont azt kérdezte amire gondolt akkor arra válaszoltam amire gondolt.

A kérdésben az szerepel hogy egy szám-n-est (n darab számot vagy ha úgy tetszik egy n elemű vektort) leképez egy számmá, ahol mindegyik R azaz valós számokról van szó. Vagy máshogy mondva olyan függvényekről szól általánosságban a kérdés melyeknek az értelmezési tartománya n darab valós szám, értékkészlete valós szám.

Ha csak azokat a függvényeket nézzük ahol az értelmezési tartománya és az értékkészlete is valós számok halmaza azokból is több van mint amennyi algoritmus létezik. Sőt igazából pont ugyanannyi n változós valós függvény létezik mint amennyi egy változós valós függvény lézezik.

Ezek szerint nem érted kérdező. Az O(1) bonyolultságtól kezdve a kiszámíthatatlanig bármi lehet, erről szól az 1-es válasz is.

Hiszen a legtöbb matematikailag létező függvényre nem létezik még algortimus sem, azt is kifejtettem hogy miért van így.

"#5-ös, nem tudom értelmezni, amit írsz.

Mivel SAT kiterjesztésről beszélünk, így legalább olyan bonyolult a problémánk, mint a SAT, azaz NP-teljes a probléma vagy még bonyolultabb. Ezért annak semmi teteje, hogy

> Az O(1) bonyolultságtól kezdve a kiszámíthatatlanig bármi lehet, erről szól az 1-es válasz is."

A legnyilvánvalóbb abból kiindulva amit te írtál, hogy ez O(1) komplexitású eldönteni : "f(x,y) = π nem függ egyik változójától sem"

Ez is eldönthető O(1) idő alatt : f(x,y) = x+y-asinh(sinh(x))-1 és ez is f(x,y,z) = x+y+z^2 .

Természetesen úgy értem, hogy deduktív függvényellemző rendszerrel ahol inputként megkapja a formulát.

"Kérdés, hogy ez nem korlátozza-e azt, hogy bármilyen R^n -> R függvény lehessen."

Ez kérdés? Már az első hozzászólásban leírtam hogy nem lehet.

"Tegyük fel azt is, hogy bármely valós számhoz elég O(1) véges tár, amit az inputban megjelenítünk."

Ezt komolyan gondolod? Egy 0-1 közötti valós számban enkódolhatok végtelenül sok információt. Inkább dolgozz be valami tech cégnek, hogy minek veszik az adatközpontok petabájtnyi tárakat, te meg tudod oldani konstans tárral tetszőlegesen sok infomrációt tárolni. Felérne egy matematikai Nobel díjjal, már ha lenne belőle ilyen díj. Matematikailag is ellentmondásos.

Kontinuum sok olyan valós szám van amit nem lehet leírni semmilyen algoritmussal.

"Egyébként nyugodtan élhetünk a kontinuum-hipotézissel, és mondhatjuk, hogy R continuum számosságú, ill. az R->R, R^n->R függvények halmaza 2^continuum számosságú."

Ide pedig minek kell a kontinuum-hipotézis?

-------

A komplexitás pedig lehet gyakorlatilag akármennyi a kiszámítható függvények esetében is. Például van a Graham szám, ez egy sorozatnak a 64.-ik tagja méghozzá a g(64). Ezen g sorozat tagjainak a kiszámítása is túl nehéz feladat, de kisebb számokká is redukálhatom a függvényt. Python-osan írva az f függvény f = lambda x : sin(int(str(g(abs(trunc(x))))[:10])) . A g ezen g sorozat mint diszkrét függvény, a trunc egészrészre csonkítás, abs abszolút érték képzés str string-é alakítás a [:10] az első 10 karakterképzés, az int az a stringet egésszé kasztolja, a sin a sinusz függvény.

Továbbá van a kiszámíthatóságelméletben a Chaitin's konstans, valójában több ilyen konstans is létezik, az értékük nem számítható ki. Ha kiszámítható lenne akkor létezne algoritmus a megállási problémára. Ha ezeket is beleveszem, függvényt alkotok velük akkor csináltam olyan függvényeket melyek nem számíthatóak ki, így gyárthatok olyan függvényeket hogy kiszámíthatatlanok legyenek.

Továbbá pedig létezik olyan f(x) függvény, ha x racionális akkor értéke 0, ha x irracionális akkor értéke 1. Máig megoldatlan hogy e + π irracionális-e. Sőt semmilyen (n, m) egész számpárra nem ismert, hogy m*π + n*e irracionális-e. Már önmagában azt se tudom hogy ezen kérdés milyen bonyolultsági osztályba sorolandó. Egy deduktív következető rendszer le tudná e vezetni véges lépésben és ennek mi a bonyolultsági osztálya, az látható, hogy brute force-al nem megyünk semmire itt.