5 ms·

Isn't there some graph problem about finding cliques that is NP-hard (presumably NP-complete in the decision version) but that has an expected _constant_ time a

Isn't there some graph problem about finding cliques that is NP-hard (presumably NP-complete in the decision version) but that has an expected _constant_ time algorithm over the usual distribution of random graphs? I seem to remember the algorithm is something like "check a few samples at random, if that doesn't find what you're after then do exponential-time search" and the point is the chance that the samples don't find what you're after is exponentially small, because the thing you're looking for is so frequent.

CaptainNegative 3y ago
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.
- red_admiral 3y ago
  It was years ago I studied the problem and I've lost my notes, but what you say makes sense.

CaptainNegative 3y ago

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.

red_admiral 3y ago
It was years ago I studied the problem and I've lost my notes, but what you say makes sense.