Fast algorithms for Hard Problems

Anta at du er sjef i et selskap med 1000 ansatte, og at det i senere tid har oppstått såpass alvorlige personalkonflikter at den eneste måten å håndtere disse på er å sparke noen av kamphanene. Du ønsker ikke å sparke mer enn 10 ansatte. Er det mulig å sparke høyst 10 slik at ingen av de resterende ansatte har en personalkonflikt? En måte å finne ut av dette på er å lage et dataprogram som, for alle grupper på høyst 10 ansatte, sjekker om de resterende ville hatt en personalkonflikt dersom akkurat denne gruppen ble sparket. Et slikt dataprogram er ganske enkelt å lage, det er bare en hake - det vil bruke langt mer enn 1 milliard år på å finne løsningen. Innen den tid har nok personalkonfliktene blitt løst på andre måter. 

Er det mulig å lage at dataprogram som finner en løsning raskere enn ved å bare prøve alle muligheter? Dessverre er problemet ovenfor kjent som "Vertex Cover'' problemet, og derfor er det lite sannsynlig at det finnes et dataprogram som vil løse alle instanser effektivt. Men du er jo ikke interessert i å løse alle mulige instanser av Vertex Cover, du trenger kun å løse den instansen som er i hende akkurat nå. Den har gjerne ekstra strukturer som dataprogrammer kan utnytte. Parameterisert kompleksitet, feltet som Mithilesh Kumar sin avhandling er innenfor, handler om å utnytte slike strukturer for å få dataprogrammer til å kjøre raskere. I avhandlingen har Kumar sett på generaliseringer av Vertex Cover problemet (kjent som "Hitting Set'' problemer) og studert den parameteriserte kompleksiteten av disse.

Personalia:

Kumar ble født i India 13. august, 1985. Han tok sin mastergrad i teoretisk fysikk ved Indian Institute of Technology, Kanpur og master i Theoretical computer science ved Chennai Mathematical Institute, Chennai.