Shmuel Safra - Shmuel Safra

Shmuel Safra (hebrejština: שמואל ספרא) Je izraelský počítačový vědec. Je profesorem Počítačová věda na Tel Avivská univerzita, Izrael. Narodil se v Jeruzalém.

Mezi oblasti výzkumu společnosti Safra patří teorie složitosti a teorie automatů. Jeho práce v Teorii složitosti zahrnuje klasifikaci problémů aproximace - jejich předvádění NP-tvrdé i pro slabé faktory aproximace - a teorii pravděpodobnostně ověřitelné důkazy (PCP) a Věta o PCP, což dává silnější charakterizaci třídy NP prostřednictvím dokladu o členství, který lze ověřit čtením pouze konstantního počtu jeho bitů.

Jeho práce na teorii automatů zkoumá determinizaci a doplnění konečné automaty přes nekonečné řetězce, zejména složitost takového překladu pro Büchi automaty, Streett automaty a Rabinovy ​​automaty.

V roce 2001 Safra vyhrál Gödelova cena v teoretické informatice za své práce „Interaktivní důkazy a tvrdost aproximace kliky“ a „Pravděpodobnostní kontrola důkazů: nová charakteristika NP“.

Viz také

• Problém s vrcholovým krytem
• Nastavit problém s krytem

externí odkazy

• Domovská stránka společnosti Muli Safra
• Prezentace teorie výpočetní složitosti
• Shmuel Safra na Matematický genealogický projekt