Well, assuming we can somehow prevent someone from cheating and writing code to solve the problems, the confirmation wait shouldn't be any worse if people are working in pools to solve the problems and submitting found answers in an online form. If 4000 people are working for their UBI in pools the confirmations should be roughly as fast as they are today.

Again the problem would be to create challenges that "can't be computed" but can be verified with a software.