Suppose we have a small quantum computer with only M qubits. Can such a device genuinely speed up certain algorithms, even when the problem size is much larger than M? Here we answer this question to the affirmative. We present a hybrid quantum-classical algorithm to solve 3SAT problems involving n»M variables that significantly speeds up its fully classical counterpart. This question may be relevant in view of the current quest to build small quantum computers.