Innehållsförteckning:
- Vad anses vara polynomtid?
- Hur vet du om något är en polynomtid?
- Vad händer om reduktionen tillåts i exponentiell tid?
- Vad är en exponentiell algoritm?
2024 Författare: Fiona Howard | [email protected]. Senast ändrad: 2024-01-10 06:43
I beräkningskomplexitetsteori är en polynom-tidsreduktion en metod för att lösa ett problem med ett annat. Polynom-tidsreduktioner används ofta i komplexitetsteorin för att definiera både komplexitetsklasser och kompletta problem för dessa klasser. …
Vad anses vara polynomtid?
En algoritm sägs vara av polynomtid om dess körtid är övre gränsad av ett polynomuttryck i storleken på indata för algoritmen, det vill säga T(n)=O(nk) för någon positiv konstant k.
Hur vet du om något är en polynomtid?
3 svar. En algoritm är polynom (har polynom körtid) om för någon k, C>0, dess körtid på ingångar av storlek n är högst Cnk. På motsvarande sätt är en algoritm polynom om för vissa k>0, dess körtid på ingångar av storlek n är O(nk).
Vad händer om reduktionen tillåts i exponentiell tid?
Om reduktionen tillåts exponentiell tid, kan det helt lösa det ursprungliga problemet och producera en trivial instans av målproblemet Detta betyder att varje problem i NP kan reduceras till varje andra problem med sådan typ av reduktioner, så varje problem i NP är NP-komplett för exponentiella tidsreduktioner.
Vad är en exponentiell algoritm?
En algoritm sägs vara exponentiell tid, om T(n) är övre gränsen av 2poly( ) , där poly(n) är något polynom i n. Mer formellt är en algoritm exponentiell tid om T(n) begränsas av O(2nk) för någon konstant k. Ref:Wiki.
