| dbo:abstract
|
- بيسبايس PSPACE في نظرية التعقيد الحسابي قسم التعقيد هو قسم كل المسائل التي يمكن حلها بكمية موارد حدودية (polynomial space), هذه المجموعة يُعتقد انها أكبر من NP , ولهذا القسم اهمية كبيرة في حل الألعاب إذ انه مُعظم الألعاب هي PSPACE صعبة ومسألة التقرير لكثير من الألعاب هي PSPACE كاملة. (ar)
- En teoria de la complexitat, la classe de complexitat PSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing usant un espai polinòmic. (ca)
- In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können. (de)
- En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio de polinomios y tiempo ilimitado. La definición no depende del carácter determinista de la máquina de Turing (esto es un corolario del teorema de Savitch). De manera que PSPACE = NPSPACE. Si un problema se resuelve mediante un algoritmo no determinista de complejidad espacial polinómica, también se puede resolver mediante un algoritmo determinista de complejidad espacial polinómica. (es)
- In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. (en)
- En informatique théorique, plus précisément en théorie de la complexité, PSPACE est la classe de complexité des problèmes de décision décidés par une machine de Turing déterministe avec un espace polynomial. (fr)
- PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。 (ja)
- Nella teoria della complessità algoritmica, la classe di problemi PSPACE (da polynomial space) è l'insieme di tutti i problemi che possono essere risolti da una macchina di Turing deterministica usando una quantità di memoria di , dove è la dimensione dei dati di ingresso e è un qualsiasi valore finito. In altre parole, PSPACE include quei problemi che possono essere risolti da un algoritmo che utilizzi uno spazio di memoria la cui dimensione sia al più funzione polinomiale della dimensione dell'input. (it)
- 계산 복잡도 이론에서 PSPACE는 결정론적 튜링 기계나 비결정론적 튜링 기계가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 판정 문제들의 집합이다. 에 따르면 PSPACE는 NSPACE와 같기 때문에 튜링 기계가 결정론적이든 비결정론적이든 상관 없다. 가 PSPACE의 진부분집합이다. 복잡도 종류 NL, P, NP, PSPACE, EXPSPACE가 갖는 관계는 이렇다: 첫째 줄에 (부분집합) 기호가 세 개 있다. 셋 중 하나는 여야 하는데, 정확히 어느 것이 그런지는 알려진 바 없다. 수많은 사람들이 셋 모두 라고 추측하고 있다. P-NP 문제(두 번째 가 인지 아닌지 묻는 문제)에 대한 해법에는 상금 백만 달러가 걸려 있다. PSPACE에서 가장 어려운 문제들을 PSPACE-완전이라고 한다. PSPACE이고 NP는 아닐 것으로 예상되는 문제들을 알고 싶으면 PSPACE-완전을 보라. (ko)
- W teorii złożoności obliczeniowej PSPACE jest zbiorem wszystkich problemów decyzyjnych, które można rozwiązać za pomocą maszyny Turinga wykorzystującej wielomianową przestrzeń. (pl)
- In de complexiteitstheorie is PSPACE een die alle beslissingsproblemen bevat die met polynomiale ruimte opgelost kunnen worden. PSPACE kan gedefinieerd worden in termen van : . PSPACE is onder andere gelijk aan de complexiteitsklassen , en . Het bewijs voor de laatstgenoemde equivalentie, IP = PSPACE, werd geleverd door Adi Shamir. De complexiteitsklasse IP is gedefinieerd met behulp van . In juli 2009 werd bewezen dat PSPACE gelijk is aan . Enkele deelverzamelingen van PSPACE zijn P en NP. (nl)
- Na teoria da complexidade computacional, PSPACE é o conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço. (pt)
- Класс сложности PSPACE — набор всех проблем разрешимости в теории сложности вычислений, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства. (ru)
- PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。 (zh)
- PSPACE (англ. Polynomial Space — поліноміальне місце) — клас задач, які розв'язні на машині Тюрінга з використанням поліноміального запасу пам'яті. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7424 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- بيسبايس PSPACE في نظرية التعقيد الحسابي قسم التعقيد هو قسم كل المسائل التي يمكن حلها بكمية موارد حدودية (polynomial space), هذه المجموعة يُعتقد انها أكبر من NP , ولهذا القسم اهمية كبيرة في حل الألعاب إذ انه مُعظم الألعاب هي PSPACE صعبة ومسألة التقرير لكثير من الألعاب هي PSPACE كاملة. (ar)
- En teoria de la complexitat, la classe de complexitat PSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing usant un espai polinòmic. (ca)
- In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können. (de)
- En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio de polinomios y tiempo ilimitado. La definición no depende del carácter determinista de la máquina de Turing (esto es un corolario del teorema de Savitch). De manera que PSPACE = NPSPACE. Si un problema se resuelve mediante un algoritmo no determinista de complejidad espacial polinómica, también se puede resolver mediante un algoritmo determinista de complejidad espacial polinómica. (es)
- In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. (en)
- En informatique théorique, plus précisément en théorie de la complexité, PSPACE est la classe de complexité des problèmes de décision décidés par une machine de Turing déterministe avec un espace polynomial. (fr)
- PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。 (ja)
- Nella teoria della complessità algoritmica, la classe di problemi PSPACE (da polynomial space) è l'insieme di tutti i problemi che possono essere risolti da una macchina di Turing deterministica usando una quantità di memoria di , dove è la dimensione dei dati di ingresso e è un qualsiasi valore finito. In altre parole, PSPACE include quei problemi che possono essere risolti da un algoritmo che utilizzi uno spazio di memoria la cui dimensione sia al più funzione polinomiale della dimensione dell'input. (it)
- 계산 복잡도 이론에서 PSPACE는 결정론적 튜링 기계나 비결정론적 튜링 기계가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 판정 문제들의 집합이다. 에 따르면 PSPACE는 NSPACE와 같기 때문에 튜링 기계가 결정론적이든 비결정론적이든 상관 없다. 가 PSPACE의 진부분집합이다. 복잡도 종류 NL, P, NP, PSPACE, EXPSPACE가 갖는 관계는 이렇다: 첫째 줄에 (부분집합) 기호가 세 개 있다. 셋 중 하나는 여야 하는데, 정확히 어느 것이 그런지는 알려진 바 없다. 수많은 사람들이 셋 모두 라고 추측하고 있다. P-NP 문제(두 번째 가 인지 아닌지 묻는 문제)에 대한 해법에는 상금 백만 달러가 걸려 있다. PSPACE에서 가장 어려운 문제들을 PSPACE-완전이라고 한다. PSPACE이고 NP는 아닐 것으로 예상되는 문제들을 알고 싶으면 PSPACE-완전을 보라. (ko)
- W teorii złożoności obliczeniowej PSPACE jest zbiorem wszystkich problemów decyzyjnych, które można rozwiązać za pomocą maszyny Turinga wykorzystującej wielomianową przestrzeń. (pl)
- In de complexiteitstheorie is PSPACE een die alle beslissingsproblemen bevat die met polynomiale ruimte opgelost kunnen worden. PSPACE kan gedefinieerd worden in termen van : . PSPACE is onder andere gelijk aan de complexiteitsklassen , en . Het bewijs voor de laatstgenoemde equivalentie, IP = PSPACE, werd geleverd door Adi Shamir. De complexiteitsklasse IP is gedefinieerd met behulp van . In juli 2009 werd bewezen dat PSPACE gelijk is aan . Enkele deelverzamelingen van PSPACE zijn P en NP. (nl)
- Na teoria da complexidade computacional, PSPACE é o conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço. (pt)
- Класс сложности PSPACE — набор всех проблем разрешимости в теории сложности вычислений, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства. (ru)
- PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。 (zh)
- PSPACE (англ. Polynomial Space — поліноміальне місце) — клас задач, які розв'язні на машині Тюрінга з використанням поліноміального запасу пам'яті. (uk)
|
| rdfs:label
|
- بيسبايس (ar)
- PSPACE (ca)
- PSPACE (cs)
- PSPACE (de)
- PSPACE (es)
- PSPACE (fr)
- PSPACE (it)
- PSPACE (ja)
- PSPACE (ko)
- PSPACE (nl)
- PSPACE (en)
- PSPACE (pl)
- Класс PSPACE (ru)
- PSPACE (pt)
- Клас складності PSPACE (uk)
- PSPACE (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
