ω(G) is the size of max clique in G.
Recall that, for all 0 < δ1 < δ2 < 1, the following problem is NP-hard: Given a graph G with the PROMISE that either ω(G) ≤ nδ1 OR ω(G) ≥ nδ2, determine which one it is. Output NO in the first case and YES in the second case. (Reference: David Zuckerman proved the result here by derandomizing a result of Johan Hastad that had as its conclusion ZPP=NP rather than P=NP. See here for Hastad paper.)
Note the following,
If ω(G) ≥ nδ2 then, by Ramsey's Theorem and the current bounds known on the Ramsey numbers, for ANY 2-coloring of the edges of G there will be a mono clique of size (0.5)*(δ2)log n. (Slightly larger values can also be obtained.)This gives rise to the following POSSIBLE RTIME(nO(log n)) algorithm for the promise problem.
- Input G
Do the following nAlog n times Or until you get a NO.
(A is a constant that we pick later.)
- Randomly 2-color the edges of G
- Look for a mono clique of size (0.5)*(δ2)log n. (This takes nO(log n) time.)
- If you DO NOT find one then output NO and stop. (In this case you KNOW the answer is NO.)
- Otherwise try again.
- (If you got here then every coloring you tried had a mono clique of size (0.5)*(δ2)log n.) Output YES. (You are NOT SURE that this is correct.)
- IF ω(G) ≥ nδ2 then the algorithm will correctly say YES.
- IF ω(G) ≤ nδ1 then will the algorithm find a coloring that shows this? Or more precisely, will this happen with high prob?
There exists 0 < δ1 < δ2 < 1, A, and a function p(n) = nAlog n such that the following is true: For almost all graphs G with ω(G) ≤ nδ1 the prob that a rand 2-coloring of the edges will have a mono clique of size (0.5)*(δ2)log n is LESS THAN (1-p(n)). (ADDED LATER: Almost All Graphs means for all but a FINITE number of graphs.)So, what to make of this?
- One MAY think the following; Since we DO NOT think that NP is in RTIME(nO(log n)) the conjecture is false. Perhaps it can be PROVEN false (unconditionally) using the techniques of Zuckerman or Hastad, or other techniques in the area.
- Is our confidence that NP is not in RTIME(nO(log n)) SO STRONG? We could at least TRY to prove the conjecture.
- One could put the correct Ramsey Number, and a good set of coin flips, into an advice string. This would yield an algorithm in DTIME(nlog n)/poly. A slighly weaker conjecture would suffice to prove this algorithm works.