Mahaneysova věta - Mahaneys theorem - Wikipedia

Mahaneyova věta je věta v teorie výpočetní složitosti prokázal Stephen Mahaney, který uvádí, že pokud existuje řídký jazyk je NP-Complete, pak P = NP. Také pokud existuje Turingova redukce od NP-úplného řídkého jazyka k P, pak k polynomiální časová hierarchie se zhroutí do ∆_2 (NP ^ {NP [logn]}).[1]

Reference

  1. ^ Mahaney, Stephen R. (říjen 1982). "Řídké kompletní sady pro NP: Řešení domněnky Bermana a Hartmanise". Journal of Computer and System Sciences. 25 (2): 130–143. doi:10.1016/0022-0000(82)90002-2. hdl:1813/6257.