Överväg algoritmer med obegränsad beräkningstid som sonderar posterna i adjacency matris av en n vertex graf, och behöver för att producera en klick. Vi visar att om indatagrafen dras slumpmässigt från G n, 1 2 (och därmed sannolikt har en kliché av storlek ungefär 2 log n), sedan för varje δ < 2 och konstant l, finns det en α < 2 (som kan bero på δ och l) sådan att ingen algoritm som gör n δ sonder i l rundor är sannolikt (vid val av slumpmässig graf) att producera en kliché av storlek större än α log n.
Feige och al. REF visar ett omöjligt resultat om algoritmens anpassningsförmåga är begränsad: varje algoritm som gör q = O(n δ ) kantförfrågningar (δ < 2) i l rundor finner klichéer av storlek som mest (2 − ε) log n där ε = ε (ε, l) > 0.
Finding cliques using few probes
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}