I detta dokument inför vi en allmän ram för finkorniga minskningar av ungefärliga räkneproblem till deras beslutsversioner. (Så vi använder ett orakel som avgör om något vittne existerar för att multiplikativt approximera antalet vittnen med minimala overhead.) Detta speglar ett grundläggande resultat av Sipser (STOC 1983) och Stockmeyer (SICOMP 1985) i polynometid-inställningen, och ett liknande resultat av Müller (IWPEC 2006) i FPT-inställningen. Med hjälp av vårt ramverk får vi sådana minskningar för några av de viktigaste problemen i finkornig komplexitet: Orthogonal Vectors problem, 3SUM, och Negative-Weight Triangle problem (som är nära relaterat till All-Pairs Kortaste vägen). Även om alla dessa problem har enkla algoritmer över vilka det förmodas att ingen polynom förbättring är möjlig, våra minskningar skulle förbli intressant även om dessa gissningar visades; de har endast polylogaritmiska overhead, och kan därför tillämpas på subpolynomiska förbättringar såsom n 3 /exp (to( log n))-tidsalgoritm för Negative-Weight Triangle problem på grund av Williams (STOC 2014). Vårt ramverk är också tillräckligt allmänt för att gälla versioner av de problem för vilka effektivare algoritmer är kända. Till exempel kan Orthogonal Vectors problem över GF(m) d för konstant m lösas i tid n · poly(d) genom ett resultat av Williams och Yu (SODA 2014); vårt resultat innebär att vi kan ungefär räkna antalet ortogonala par med i stort sett samma körtid. Vi ger också en finkornig minskning från ungefärligt #SAT till SAT. Antag att den starka exponentiella tidshypotesen (SETH) är falsk, så att det för några 1 < c < 2 och alla k finns en O (c n ) tidsalgoritm för k- SAT. Sedan bevisar vi att för alla k finns det en O(c +o(1)) n )-tidsalgoritm för ungefärlig #k-SAT. I synnerhet, vårt resultat innebär att Exponential Time Hypothesis (ETH) är likvärdig med den till synes svagare uttalande att det inte finns någon algoritm för att approximera #3-SAT till inom en faktor på 1 + ε i tid 2 o(n) /ε 2 (ta ε > 0 som en del av inmatningen). En fullständig version av detta dokument med detaljerade bevis finns på https://arxiv.org/ abs/1707.04609.
Dell och Lapinskas REF använde kantuppskattning för att få ungefärliga beräkningsalgoritmer för problem i finkornig komplexitet.
Fine-grained reductions from approximate counting to decision
{'venue': 'STOC 2018', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}