Ha (N)L-ben a polinomidejű visszavezetés nem elég erős, csak a logtáras, akkor (N)EXP-ben nem túl erős?

Figyelt kérdés

P-ben és NP-ben a problémákat polinomidőben vezetjük vissza egymásra, L-ben és NL-ben logtáras visszavezetés van, akkor EXP-ben és NEXP-ben nem kellene valami exponenciális visszavezetés?

#polinom #visszavezetés #bonyolultságelmélet #polinomidejű #logtár

2022. márc. 28. 22:45

1/1 anonim

válasza:

De kellene. Te nem Balázs vagy?

2022. márc. 29. 07:55

Hasznos számodra ez a válasz?

Kapcsolódó kérdések:

Adójóváírás visszavezetése komcsi tempó?

Támogatjátok a közös vállalat visszavezetését?

Topológiailag megoldható a Duna visszavezetése az eredeti medrébe?

Hogyan kell a MAXFTN problémát visszavezetni a 3SZÍN problémára?

Nem tudom, hogy hogy kell kiszámolni. Ha egy osztalyban 25-en vannak es annak a 24%-a 4-est irt akkor hogy tudnám levezetni, hogy hányan irtak 4-es dolgozatot?

Legalább hány függvény/operátor/metódus lenne szükséges, hogy az összes többit definiálhassuk velük?

Tudományok főkategória kérdései »

Tudományok - Alkalmazott tudományok kategória kérdései »

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!