/sci/ - Science & Math » Thread #12327457

31KiB, 1844x623, 1_D_1tbv_wNFJ-rrremAGX4Q.png

View Same Google iqdb SauceNAO

Anonymous Tue 10 Nov 20:09:06 2020 No.12327457 View Reply Original Report

Quoted By: >>12327529 >>12327986 >>12329974

How the fuck can we still not know what is the asymptotically optimal algorithm for square matrix multiplication?

Anonymous

Anonymous Tue 10 Nov 2020 20:10:02 No.12327467 Report

Quoted By: >>12327473 >>12327986 >>12329792

it's really hard to prove lower complexity bounds

Anonymous

Anonymous Tue 10 Nov 2020 20:11:07 No.12327473 Report

Quoted By: >>12327476 >>12327527 >>12327986

>>12327467
That's not what I asked, fuckwad.

Anonymous

Anonymous Tue 10 Nov 2020 20:12:52 No.12327476 Report

Quoted By: >>12327495

>>12327473
Wh..what do you think asymptotically optimal would mean.

Anonymous

Anonymous Tue 10 Nov 2020 20:16:26 No.12327495 Report

Quoted By: >>12327561

>>12327476
>In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor worse than the best possible algorithm.

Anonymous

Anonymous Tue 10 Nov 2020 20:22:37 No.12327527 Report

Quoted By:

>>12327473
>fuckwad
rude

Anonymous

Anonymous Tue 10 Nov 2020 20:24:24 No.12327529 Report

Quoted By:

>>12327457
Because you memed yourselves into hating what you don't understand.

Anonymous

Anonymous Tue 10 Nov 2020 20:34:28 No.12327561 Report

Quoted By:

>>12327495
how do you think we would prove what the best possible algorithm would be without proving some sort of lower-bound on the complexity (either directly or as a byproduct)?

Anonymous

Anonymous Tue 10 Nov 2020 22:20:16 No.12327986 Report

Quoted By:

>>12327457
>>12327467
>>12327473

>asks profound mathematical question.
>too stupid to understand the question
OP BTFO

Anonymous

Anonymous Wed 11 Nov 2020 11:34:30 No.12329792 Report

Quoted By: >>12330188

>>12327467
BUT WHY

Anonymous

Anonymous Wed 11 Nov 2020 13:17:37 No.12329974 Report

Quoted By:

>>12327457
>CW algorithm
ultra fast for matrices that are "impractically large" (which probably would be sparse anyways)

Anonymous

Anonymous Wed 11 Nov 2020 15:13:13 No.12330188 Report

Quoted By:

>>12329792
it's easy to prove an upper bound: give an example.
it's hard to prove a lower bound because an example doesn't prove anything in this case

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches