Neelementární problém - Nonelementary problem
v teorie výpočetní složitosti, a neelementární problém[1] je problém, který není členem třídy ZÁKLADNÍ. Jako třída je někdy označována jako NONELEMENTARY.
Mezi příklady neelementárních problémů, které jsou přesto rozhodující, patří:
- problém ekvivalence regulárního výrazu s doplňováním[2]
- rozhodovací problém pro monadická logika druhého řádu přes stromy[3]
- rozhodovací problém pro termínové algebry[4]
- uspokojivost W. V. O. Quine skládaný fragment logika prvního řádu[5]
Reference
- ^ Vorobyov, Sergei; Voronkov, Andrie (1998), „Složitost nerekurzivních logických programů se složitými hodnotami“, Sborník ze sedmnáctého sympozia ACM SIGACT-SIGMOD-SIGART o zásadách databázových systémů (PODS '98), New York, NY, USA: ACM, s. 244–253, CiteSeerX 10.1.1.39.8822, doi:10.1145/275487.275515, ISBN 978-0-89791-996-8.
- ^ Stockmeyer, Larry J. (1974), Složitost rozhodovacích problémů v teorii a logice automatů (PDF), Ph.D. disertační práce, Massachusetts Institute of Technology
- ^ Libkin, Leonid (2006), „Logics for unranked trees: an overview“, Logické metody v informatice, 2 (3): 3:2, 31, arXiv:cs.LO / 0606062, doi:10.2168 / LMCS-2 (3: 2) 2006, PAN 2295773.
- ^ Vorobyov, Sergei (1996), „Vylepšená dolní mez pro základní teorie stromů“, Automated Deduction - Cade-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, 30. července - 3. srpna 1996, sborník, Přednášky v informatice, 1104, Springer, str. 275–287, CiteSeerX 10.1.1.39.1499, doi:10.1007/3-540-61511-3_91, ISBN 978-3-540-61511-8.
- ^ „Quinin flétnový fragment je neelementární“ (PDF).
| P ≟ NP | Tento teoretická informatika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |