Matematiker præsenterer et bevis på følsomhedsformodningen

Sensitivitetsformodningen har stået som en af ​​de vigtigste, og forvirrende, åbne problemer inden for teoretisk datalogi i næsten tre årtier. Det ser ud til endelig at have mødt sin match gennem arbejde af Hao Huang, en assisterende professor i matematik ved Emory University.

Huang vil præsentere et bevis på følsomhedsformodningen under den internationale konference om tilfældige strukturer og algoritmer, indstillet til Zürich, Schweiz, 15 til 19 juli.

"Jeg har angrebet dette problem af og til siden 2012, "Huang siger, "men nøgleideen dukkede op for mig for cirka en uge siden. Jeg fandt endelig det rigtige værktøj til at løse det."

Huang postede beviset på sin hjemmeside, og det skabte snart buzz blandt matematikere og dataloger på sociale medier, som har rost dens bemærkelsesværdige kortfattethed og enkelhed.

Sensitivitetsformodningen vedrører booleske data, som kortlægger information til en sand-falsk, eller 1-0 binært. Booleske funktioner spiller en vigtig rolle i kompleksitetsteori, samt i design af kredsløb og chips til digitale computere.

"I matematik, en boolsk funktion er et af de mest grundlæggende diskrete emner – ligesom tal, grafer eller geometriske former, " forklarer Huang.

Der er mange kompleksitetsmål for en boolsk funktion, og næsten alle – inklusive beslutningstræets kompleksitet, certifikatets kompleksitet, den randomiserede forespørgselskompleksitet og mange andre - er kendt for at være polynomielt relateret. Imidlertid, der er et ukendt tilfælde, den såkaldte følsomhed af en boolesk funktion, som måler, hvor følsom funktionen er, når man ændrer en indgang ad gangen.

I 1994, matematikerne Noam Nisan og Mario Szegedy foreslog følsomhedsformodningen vedrørende denne ukendte sag.

"Deres formodning siger, at følsomheden af ​​en boolesk funktion også er polynomielt relateret til de andre mål, " siger Huang. "Hvis det er sandt, så ville det ophøre med at være en outlier, og det ville slutte sig til resten af ​​dem."

Huang udviklede en algebraisk metode til at bevise formodningen. "Jeg håber, at denne metode også kan have et vist potentiale til at blive anvendt på andre kombinatoriske og kompleksitetsproblemer, der er vigtige for datalogi, " han siger.