Vi presenterar funktioner som kan beräknas i någon xed polynom tid men är hårt i genomsnitt för alla algoritmer som körs i något mindre tid, antar allmänt förmodade värsta fall hårdhet för problem från studien av ne-grained komplexitet. Ovillkorliga konstruktioner av sådana funktioner är kända från tidigare (Goldmann et al., IPL '94), men dessa har varit kanoniska funktioner som inte har fått vidare användning, medan våra funktioner är nära relaterade till välstuderade problem och har betydande algebraisk struktur. Baserat på den genomsnittliga hårdheten och strukturella egenskaperna hos våra funktioner, beskriver vi konstruktionen av ett Proof of Work schema och diskuterar möjliga metoder för att bygga ne-grained OneWay funktioner. Vi visar också hur våra minskningar gör gissningar om den värsta-fall hårdhet av de problem vi minskar från (och följaktligen den starka Exponential Time Hypothesis) heuristically falsi kan i en mening liknar den (Naor, CRYPTO '03). Vi bevisar vår hårdhet resultat i varje fall genom att visa negrained minskningar från att lösa ett av tre problem -nämligen Orthogonal Vectors (OV), 3SUM, och All-Pairs Shortest Paths (APSP) - i värsta fall att beräkna vår funktion korrekt på en jämnt slumpmässig inmatning. Den förmodade hårdheten hos OV och 3SUM ger oss sedan funktioner som kräver n 2‐o (1) tid att beräkna i genomsnitt, och APSP ger oss en funktion som kräver n 3‐o (1) tid. Med hjälp av samma tekniker får vi också en villkorlig medeltidshierarki av funktioner.
Nyligen, REF använt polynom slumpmässiga självreducerbarhet resultera i finkornig inställning för att konstruera polynomials som är svåra att utvärdera på de flesta ingångar, förutsatt finkorniga hårdhet gissningar för problem som 3-SUM, Orthogonal-Vektorer, och / eller All-Pairs-Shortest-Paths.
Average-case fine-grained hardness
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Materials Science']}