Offer 01€5Danupon Nanongkai
Personal offerThe official page reserves each cash prize for the first solver. No expiry is displayed for this €5 question; confirm before relying on the offer.
01
The problem
In a Turing-machine or RAM model, determine whether a decision problem P can have a 10n-time algorithm, a particular 100n²-time algorithm A, yet every 10n-time algorithm for P has a description strictly larger than A.
Open sinceUnknowndate not stated by sponsor
Last checked2026.07.27Catalog verification
02
Reward offers
03
Sources & reading
1 unique reference linksSponsor’s current Open € page ↗