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.
Minskningen från REF visar att både BMM och girth har verkligt subkubiska kombinatoriska algoritmer, eller ingen av dem gör det.
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}