Vi hävdar att det i samband med biologi-inspirerade problem inom datavetenskap, förutom att studera tids komplexiteten i lösningar är också viktigt att studera urval komplexitet, ett mått på hur troligt en given algoritmisk strategi är att uppstå i naturen. I denna anda föreslår vi en urval komplexitet metrisk χ för ANTS-problemet [Fenerman et al.]. För algoritm A definierar vi χ(A) = b + log, där b är antalet minnesbitar som används av varje agent och begränsar finheten av tillgängliga sannolikheter (agenter använder sannolikheter på minst 1/2 ). Vi anser att n agenter söker efter ett mål i planet, inom ett (okänd) avstånd D från ursprunget. Vi identifierar logg D som en avgörande tröskel för vårt urval komplexitetsmått. Vi visar en ny övre gräns som uppnår nästan optimal hastighetsuppgång av (D 2 /n + D) · 2 O( ) för χ(A) ≤ 3 log log D + O(1), vilket är asymptotiskt optimalt om O(1). Som jämförelse, tidigare algoritmer som uppnår liknande upphastighet kräver χ(A) =  och (log D). Vi visar att denna tröskel är tight genom att bevisa att om χ(A) < log log D −  och sedan med stor sannolikhet målet inte hittas om varje agent utför D 2−o(1) flyttar. Detta utgör ett stort gap till den okomplicerade (D 2 /n + D) nedre gränsen.
ANTS-problemet studerades vidare av Lenzen et al., som undersökte effekterna av att begränsa minnet samt omfattningen av tillgängliga sannolikheter för agenterna REF.
Trade-offs between selection complexity and performance when searching the plane without communication
{'venue': "PODC '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}