If you're allowing for some error probability, then the answer is trivially yes. For example, the NP-Complete problem of "does this graph have a clique of size

If you're allowing for some error probability, then the answer is trivially yes. For example, the NP-Complete problem of "does this graph have a clique of size sqrt(n)" is trivial over G(n, 1/2) random graphs, because the answer is No with overwhelming probability (something decaying exponentially in n or n^2). So you don't have to read the input before responding. If you're referring to Las Vegas style (always correct) algorithms, then I don't think something along those lines can work. Reading a constant number t bits from a G(n,p) random graph yields each possible event with the constant probability (1/2)^t. So the expected running time is still at least some (small) constant times that of the failure case, which is still exponential. Are you perhaps thinking of the average case problem Planted Clique, where the task is to distinguish between a "clean" random graph G(n, 1/2) and a "planted" one where we force some random set of, say, k=n^(1/3) vertices to induce a clique? While distinguishing a graph with a k-clique from one without one is NP-hard on general graphs, you can show that G(n, 1/2) graphs virtually never contain cliques as large as 3 log n, and hence brute force searching all 3 log n sized subsets of vertices for cliques (in subexponential time n^(3 log n)) will almost always lead you to the correct answer. And once you find a clique of size 3 log n, expanding it to n^(1/3) can be done quickly using a greedy algorithm.