Gegeven een algoritme A, dat in O(2n) het probleem X oplost. Welke van de volgende beweringen zijn dan zeker waar?

De eerste bewering is waar: er is een algoritme dat X in O(2n) oplost, dus uit de definitie van TIME(f(n)) volgt dat X ∈ TIME(2n).

De tweede bewering is niet waar: het feit dat er een exponentieel algoritme bestaat voor X wil niet zeggen dat er geen polynomiaal algoritme voor X bestaat. X kan in P zitten.


De derde bewering is ook onjuist: er zijn problemen met een exponentieel algoritme die niet in NP zitten.


De vierde bewering is juist: als er met de huidige technologie een probleem ter grootte van m kan worden opgelost, kan met een twee keer zo snelle computer een probleem ter grootte van m + 1 worden opgelost.