RE (složitost) - RE (complexity)

v teorie vypočítatelnosti a teorie výpočetní složitosti, RE (rekurzivně spočetné ) je třída z rozhodovací problémy pro které může odpověď „ano“ ověřit a Turingův stroj v konečném čase.[1] Neformálně to znamená, že pokud je odpověď na problémovou instanci „ano“, pak existuje nějaký postup, který to vyžaduje konečný čas, a tento postup nikdy falešně nehlásí „ano“, pokud je skutečná odpověď „ne“. Pokud je však skutečná odpověď „ne“, postup se nemusí zastavovat; může jít donekonečná smyčka „pro některé případy„ ne “. Takový postup se někdy nazývá a semi-algoritmus, aby se odlišil od algoritmus, definovaný jako kompletní řešení rozhodovacího problému.[2]

Ekvivalentně RE je třída problémů s rozhodováním, pro kterou může Turingův stroj postupně seznamovat všechny instance „ano“ (to znamená „enumerable“). RE je rekurzivně vyčíslitelná množina a proto a Diophantine set.

Podobně, jádro je sada všech jazyků, které doplňují jazyk v RE. V jistém smyslu, jádro obsahuje jazyky, jejichž členství lze v konečném čase vyvrátit, ale prokázání členství může trvat věčně.

Vztahy k jiným třídám

Sada rekurzivní jazyky (R) je podmnožinou obou RE a jádro.[3] Ve skutečnosti jde o průsečík těchto dvou tříd, protože můžeme rozhodnout o jakémkoli problému, pro který existuje rozpoznávač a také spoluvlastník, jednoduchým prokládáním, dokud jeden nezíská výsledek. Proto:

.

Naopak sada jazyků, které nejsou ani jedno, ani druhé RE ani jádro je známý jako NRNC. Jedná se o sadu jazyků, u nichž nelze v konečném čase prokázat ani členství, ani nečlenství, a obsahují všechny ostatní jazyky, které nejsou ani v jednom RE nebo jádro. To je:

.

Nejen, že jsou tyto problémy nerozhodnutelné, ale ani oni, ani jejich doplňky nejsou rekurzivně spočetné.

V lednu 2020 preprint oznámil důkaz RE byl ekvivalentní třídě MIP * (třída, kde klasický ověřovatel interaguje s více všemocnými kvantovými provery, kteří sdílejí zapletení).[4]

RE-kompletní

RE-kompletní je sada rozhodovacích problémů, které jsou pro RE. V jistém smyslu jde o „nejtěžší“ rekurzivně spočetné problémy. Obecně platí, že na použité redukce není kladeno žádné omezení, kromě toho, že musí být mnoho-jedna redukce.

Příklady RE-úplných problémů:

  1. Zastavení problému: Zda program s konečným vstupem běží, nebo bude spuštěn navždy.
  2. Podle Riceova věta, rozhodování o členství v jakékoli netriviální podmnožině sady rekurzivní funkce je RE-tvrdý. Bude kompletní, kdykoli je sada rekurzivně vyčíslitelná.
  3. John Myhill  (1955 )[5] dokázal to všechno kreativní sady jsou RE-kompletní.
  4. Uniformu slovní úloha pro skupiny nebo poloskupiny. (Opravdu slovní úloha pro některé jednotlivé skupiny je RE-kompletní.)
  5. Rozhodování o členství obecně neomezený formální gramatika. (Opět platí, že některé jednotlivé gramatiky mají RE- úplné problémy s členstvím.)
  6. The platnost problém pro logika prvního řádu.
  7. Problém s korespondencí: Vzhledem k seznamu párů řetězců určete, zda existuje výběr z těchto párů (umožňující opakování) tak, že zřetězení prvních položek (z dvojic) se rovná zřetězení druhých položek.
  8. Určení, zda a Diophantine rovnice má nějaké celočíselné řešení.

co-RE-kompletní

co-RE-kompletní je sada rozhodovacích problémů, které jsou pro jádro. V jistém smyslu se jedná o doplňky nejtěžších rekurzivně vyčíslitelných problémů.

Příklady problémů se společným dokončováním:

  1. The Domino problém pro Wang dlaždice.
  2. The uspokojivost problém pro logika prvního řádu.

Viz také

Reference

  1. ^ Složitost Zoo: Třída RE
  2. ^ Korfhage, Robert R. (1966). Logika a algoritmy s aplikacemi pro počítačové a informační vědy. Wiley. p.89. Metoda řešení se bude jmenovat a semi-algoritmus za [problém] P na [zařízení] M pokud řešení P (pokud existuje) se objeví po provedení konečně mnoha kroků. Semi-algoritmus se bude nazývat algoritmus pokud navíc vždy, když problém nemá řešení, metoda umožňuje zařízení to určit po konečném počtu kroků a zastaveních.
  3. ^ Složitost Zoo: Třída co-RE
  4. ^ Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2020). "MIP * = RE". arXiv:2001.04383 [kvant. ph ].
  5. ^ Myhill, Johne (1955), "Kreativní sady", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1 (2): 97–108, doi:10,1002 / malq.19550010205, PAN  0071379.