.mau.
to
dewdney-ita
ruly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs - https://arxiv.org/abs/261... . Al momento è assolutamente inutile all'atto pratico, ma per quanto mi riguarda è un risultato DAVVERO nuovo e non rimasticato recuperando roba in giro.
ruly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs - https://arxiv.org/abs/261... . Al momento è assolutamente inutile all'atto pratico, ma per quanto mi riguarda è un risultato DAVVERO nuovo e non rimasticato recuperando roba in giro.
2 days ago
-
Comment
-
Hide
-
-
[ 1 ]
-
[ 0 ]
- (Edit | Remove)
- More...
Comment
al volo: 3SUM, come spiega https://en.wikipedia.org/... , chiede la complessità computazionale di scoprire se dato un insieme di n elementi ce ne sono tre la cui somma è 0. È abbastanza facile trovare un algoritmo che richiede O(n^2) operazioni per verificarlo; nel 2014 si è trovato un algoritmo che richiede qualcosina in meno, ma molto poco; insomma richiede più di O(n^(2-epsilon)) operazioni per ogni epsilon maggiore di zero. Ora Anthropic ha trovato (pare per caso mentre gli facevano cercare altro) un algoritmo che arriva a O(n^1,998) operazioni. Non solo nessuno se lo aspettava, ma il procedimento, anche se in un certo senso di tipo classico (siamo sempre sul divide et impera) pare essere nuovo, nel senso che si accorge che non servono fare certi conti ed è per questo che si scende sotto il limite. Credo che sia il primo vero NUOVO risultato di un'IA.
-
.mau.
-
[ 1 ]
-
[ 0 ]
- (Edit | Remove)
(ovviamente non serve a nulla abbassare così il limite, ma da un punto di vista teorico è un terremoto)
-
.mau.
-
[ 0 ]
-
[ 0 ]
- (Edit | Remove)
