User:Beginner 25/Minimálautomata

A Wikipédiából, a szabad lexikonból.

A komplexitás elméletben egy komplexitás osztály a komplexitással kapcsolatos problémák egy halmaza. Egy tipikus komplexitási osztályt a következő formában definiálhatunk:

egy M absztrakt géppel és O(f(n)) R erőforrás (ahol n a bemenet hossza) felhasználásával megoldható problémák halmaza

Például, az NP osztály a döntési probléma típusú problémák halmaza, amelyek egy nemdeterminisztikus Turing-géppel, polinomiális időben megoldható. Ugyanakkor az PSPACE osztály is a döntési problémák halmaza, viszont egy determinisztikus Turing-géppel és polinomiális terület használatával oldhatók meg. Néhány komplexitási osztály a funkcionális probléma típusú problémák halmaza, mint a az FP.

Több komplexitási osztály a matematikai logika kifejezéseivel jellemezhető, lásd: deszkriptív komplexitás.

A komplexitás meghatározására a Blum axióma használható annélkül, hogy a konkrét kiszámítási modelre hivatkozni kellene.

Tartalomjegyzék

[szerkesztés] A komplexitás osztályok közötti kapcsolatok

A következő ábra a problémák (vagy nyelvek vagy nyelvtanok) néhány osztályát mutatja a komplexitási elméleti meggondolások alapján. Ha egy X osztály valódi részhalmaza Y-nak, akkor Y-al folyamatos vonal köti össze X-et. Ha X ugyan részhalmaz, de nem tudjuk, hogy azonos halmaz-e, akkor szaggatott vonal az összekötő. Technikailag a megoldható vagy megoldhatatlan csoportra való szétválasztás inkább a kiszámíthatósági elmélethez közelebbi kapcsolatot mutat, de segíti a komplexitási osztályok közötti eligazodást.

Döntési Probléma
image:solidLine.png image:solidLine.png
Type 0 (Rekurzívan felsorolható)
Nem eldönthető
image:solidLine.png
Eldönthető
image:solidLine.png
EXPSPACE
image:dottedLine.png
EXPTIME
image:dottedLine.png
PSPACE
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
Type 1 (Környezetfüggő)
image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
PSPACE-teljes
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
image:solidLine.png image:solidLine.png
Co-NP
image:dottedLine.png
NP
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
image:solidLine.png image:solidLine.png image:dottedLine.png
BPP
BQP
NP-teljes
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
image:solidLine.png image:solidLine.png
P
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png
image:solidLine.png
NC
P-teljes
image:solidLine.png image:solidLine.png
Type 2 (Környezet független)
image:solidLine.png
Type 3 (Szabályos)

[szerkesztés] Egyéb angol nyelvű anyagok

  • The Complexity Zoo: Egy hatalmas lista a komplexitási osztályokról, referencia a szakértők számára.
  • Diagram A Neil Immerman által készített diagramm megmutatja a komplexitási osztályok hierarchiáit.
  • Garey, Michael R. és David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979.


A komplexitási elméletben L egy komplexitási osztály, amelyhez olyan döntési probléma csoportok tartoznak, amelyek determinisztikus Turing-géppel és logaritmikus memoria terület felhasználásával megoldhatóak. Jó közelítéssel, a logaritmikus terület elég helyet biztosít arra, hogy állandó számú, a bementehez tartozó pointert és logartimikus számú logikai jelzőt tároljon.

A generalization of L is NL, which is the class of languages decidable in logarithmic space on a nemdeterminisztikus Turing-gép. We then trivially have L \subseteq NL. Also, a decider using O(log n) space cannot use more than 2O(log n)=nO(1) time, because this is the total number of possible configurations; thus, L \subseteq P, where P is the class of problems solvable in deterministic polynomial time.

Az L-ben lévő összes probléma megoldható log-space reductionkkal; since this is useless, weaker reductions are defined which allow identification of stronger complete problems in L, but there is no generally accepted definition of L-complete.

A komplexitás nagyon fontos problémái közé tartoznak a L = P és L = NL típusú kérdések.

The related class of function problems is FL. FL is often used to define logspace reductions.

A breakthrough October 2004 paper by Omer Reingold showed that USTCON, the problem of whether there exists a path between two vertices in a given irányítatlan gráf, is in L, establishing that L = SL, since USTCON is SL-complete.

One consequence of this is a simple logical characterization of L: it contains precisely those languages expressible in first order logic with an added commutative transitive closure operator (in graph theoretical terms, this turns every connected component into a clique).

L önmagában alacsony komlexitású, mivel szimulálható it can simulate log-space oracle queries (roughly speaking, "function calls which use log space") in log space, reusing the same space for each query.

[szerkesztés] Angol nyelvű hivatkozások

  • Christos Papadimitriou, "Computational Complexity", Addison Wesley, 1st edition, 1993, ISBN 0201530821. Chapter 16: Logarithmic space, pp.395–408.
  • Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.
  • Michael Sipser, "Introduction to the Theory of Computation", PWS Publishing, 1997, ISBN 0-534-94728-X. Section 8.4: The Classes L and NL, pp.294–296.
  • Michael R. Garey és David S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0716710455. Section 7.5: Logarithmic Space, pp.177–181.


[szerkesztés] IT

Information technology (IT) or Information and communication(s) technology (ICT) is a broad subject concerned with technology and other aspects of managing and processing information, especially in large organizations.

In particular, IT deals with the use of electronic computers and computer software to convert, store, protect, process, transmit, and retrieve information. For that reason, computer professionals are often called IT specialists, and the division of a company or university that deals with software technology is often called the IT department. Other names for the latter are information services (IS) or management information services (MIS).