Vi säger en algoritm på n × n matriser med heltal poster i [-M, M] (eller n-node grafer med kantvikter från [-M, M]) är verkligen subkubisk om det körs i O (n 3-δ · poly (log M )) tid för vissa δ > 0. Vi definierar ett begrepp om subkubisk reducibilitet och visar att många viktiga problem på grafer och matriser som kan lösas i O (n 3 ) tid är likvärdiga under subkubiska minskningar. Nämligen, följande viktade problem antingen alla har verkligen subkubiska algoritmer, eller ingen av dem gör: • De alla-par kortaste vägar problem på viktade digrafer (APSP). • Upptäcka om en viktad graf har en triangel med negativ total kantvikt. • Lista upp till n 2.99 negativa trianglar i en kantvägd graf. • Hitta en minimiviktcykel i ett diagram över icke-negativa kantvikter. • Ersättningsvägar problem på viktade digrafer. • Hitta den näst kortaste enkla vägen mellan två noder i en viktad digraf. • Kontrollera om en given matris definierar ett mått. • Verifiera riktigheten av en matris produkt över (min, +)-semiring. • Hitta en maximal subarray i en given matris. Därför, om APSP inte kan lösas i n 3−ε tid för någon ε > 0, då många andra problem behöver också i huvudsak kubik tid. I själva verket visar vi generiska ekvivalenser mellan matrisprodukter över en stor klass av algebraiska strukturer som används i optimering, verifiera en matris produkt över samma struktur, och motsvarande triangel detektionsproblem över strukturen. Dessa ekvivalenser förenklar tidigare arbete på subkubiska algoritmer för alla-par sökvägar problem, eftersom det nu räcker att ge lämpliga subkubiska triangeln detektionsalgoritmer. Andra konsekvenser av vårt arbete är nya kombinatoriska metoder för Boolesk matris multiplikation över (OR,AND)-semiring (förkortas som BMM). Vi visar att praktiska framsteg i triangeldetektering skulle innebära praktiska BMM-algoritmer, bland annat resultat. Med utgångspunkt i våra tekniker ger vi två förbättrade BMM-algoritmer: en derandomisering av den kombinatoriska BMM-algoritmen för Bansal och Williams (FOCS'09) och en förbättrad kvantalgoritm för BMM.
Vassilevska Williams och Williams REF visade sig vara en subkubisk ekvivalens mellan problemet med kombinatoriska ersättningsvägar i oviktade riktade grafer och problemet med kombinatorisk booleansk multiplikation (BMM).
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}