PSPACE-complete
http://dbpedia.org/resource/PSPACE-complete an entity of type: WikicatComplexityClasses
Em teoria da complexidade computacional, um problema de decisão é PSPACE-completo se pertence à classe de complexidade PSPACE e todos os problemas em PSPACE podem ser reduzidos a ele em tempo polinomial. Os problemas PSPACE-completos podem ser vistos como os problemas mais difíceis em PSPACE, porque uma solução para qualquer problema PSPACE-completo pode ser facilmente utilizada para resolver qualquer outro problema em PSPACE. Em geral, acredita-se que tais problemas não pertencem às famosas classes de complexidade P e NP, mas isso ainda é desconhecido. Sabe-se que eles estão fora da pequena classe de problemas NC, já que NC está contido em PolyL = DSPACE((log n)O(1))), que está estritamente contido em PSPACE pelo teorema da hierarquia de espaço.
rdf:langString
في نظرية التعقيد الحسابي، مجموعة مسائل التقرير بيسبايس-كاملة (بالإنجليزية: PSPACE-complete) هي مسائل تابعة لقسم التعقيد PSPACE، بحيث يمكن أن تختصر كل مسألة في PSPACE اليها بوقت متعدد الحدود (انظر التعقيد الكامل).
rdf:langString
En teoria de la complexitat, la classe de complexitat PSPACE-Complet és la classe dels problemes de decisió que es poden resoldre amb un espai de memòria polinòmic respecte la mida de l'entrada i si tot problema que es pot resoldre en espai polinòmic es pot reduir a aquest en un temps polinòmic. Els problemes que son PSPACE-complet es poden veure com els problemes més difícils de la classe PSPACE. L'exemple més conegut de problema dins de PSPACE-complet és el problema SAT. Una variant d'aquest problema, el conegut com el problema de la (QBF o TQBF). Aquest problema consisteix en trobar:
rdf:langString
En teoría de la complejidad computacional, la clase de complejidad PSPACE-completo (PSPACE-complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial. Los problemas en PSPACE-completo pueden verse como los problemas más difíciles de la clase PSPACE. Se sospecha fuertemente que estos problemas están fuera de las clases de complejidad P y NP, pero no hay prueba de ello. Se sabe que no están contenidos en la clase NC.
rdf:langString
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.
rdf:langString
계산 복잡도 이론에서 PSPACE-완전은 복잡도 종류이다. 판정 문제는 PSPACE에 들어 있고, 모든 PSPACE 문제가 이 문제로 될 수 있으면 PSPACE-완전이 된다. PSPACE-완전에 드는 문제는 PSPACE에서 가장 어려운 문제로 볼 수 있다. 이 문제들은 P나 NP의 범위 바깥에 있을 것으로 보이지만, 아직 증명되지는 않았다. PSPACE-완전이 NC 바깥에 있다는 것은 증명되었다. NP-완전에 들어간다고 밝혀진 첫 문제는 충족 가능성 문제(SAT)이다. 논리식이 참이 되도록 변수값을 할당할 수 있는지를 묻는 문제이다. 예를 들어, 다음 논리식을 참이 되게 할 수 있는지를 물을 수 있다. SAT 문제는 문제로 일반화할 수 있다. 이 문제는 가장 기본이 되는 PSPACE-완전 문제이다. 이 문제의 인스턴스는 전칭기호를 허용한다는 점을 빼면 SAT하고 비슷하다. 다른 PSPACE-완전 문제로는 주어진 문자열이 으로 정의한 어떤 언어에 들어가는지를 판정하는 문제가 있다.
rdf:langString
rdf:langString
مسائل PSPACE كاملة
rdf:langString
PSPACE-complet
rdf:langString
PSPACE-completo
rdf:langString
PSPACE-완전
rdf:langString
PSPACE-complete
rdf:langString
PSPACE-completude
xsd:integer
54685
xsd:integer
1118635274
rdf:langString
En teoria de la complexitat, la classe de complexitat PSPACE-Complet és la classe dels problemes de decisió que es poden resoldre amb un espai de memòria polinòmic respecte la mida de l'entrada i si tot problema que es pot resoldre en espai polinòmic es pot reduir a aquest en un temps polinòmic. Els problemes que son PSPACE-complet es poden veure com els problemes més difícils de la classe PSPACE. L'exemple més conegut de problema dins de PSPACE-complet és el problema SAT. Una variant d'aquest problema, el conegut com el problema de la (QBF o TQBF). Aquest problema consisteix en trobar: Alguns problemes d'aquesta classe son semblants a jocs i la pregunta a respondre és del tipus "existeix algun moviment que un jugador pugui fer, tal que tots els moviments del seu adversari facin que el primer jugador pugui guanyar?". Hi ha força exemples de jocs i trencaclosques que entren dins aquesta classe de complexitat.
rdf:langString
في نظرية التعقيد الحسابي، مجموعة مسائل التقرير بيسبايس-كاملة (بالإنجليزية: PSPACE-complete) هي مسائل تابعة لقسم التعقيد PSPACE، بحيث يمكن أن تختصر كل مسألة في PSPACE اليها بوقت متعدد الحدود (انظر التعقيد الكامل). أي هذه المسائل هي المسائل الأصعب في القسم PSPACE من جهة أن حل هذه المسائل بسرعة -أي وقت الخوارزمية متعدد الحدود بالنسبة للمدخل - يفضي لحل كثير من المسائل المشابهة. حَدَسَ العلماء أن مثل هذه المسائل لاتتبع اقسام التعقيد P وNP، ولكن لا نعرف صحة هذا الحدس. ولكنها تقع خارج القسم ، وذلك لأنَّ «إن سي» مجموعة جزئية للقسم ، وهذه القسم الاخير، أي PolyL , مجموعة جزئية فعلية (proper subset) ل-PSPACE .
rdf:langString
En teoría de la complejidad computacional, la clase de complejidad PSPACE-completo (PSPACE-complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial. Los problemas en PSPACE-completo pueden verse como los problemas más difíciles de la clase PSPACE. Se sospecha fuertemente que estos problemas están fuera de las clases de complejidad P y NP, pero no hay prueba de ello. Se sabe que no están contenidos en la clase NC. El problema más básico de PSPACE-completo es el problema de las tautologías booleanas que es muy parecido a SAT salvo que se quiera saber si todas las asignaciones de variables de una expresión booleana hacen que la expresión sea cierta. En teoría de complejidad, un problema de decisión es PSPACE-completo cuando pertenece a la clase de complejidad PSPACE y cada problema en PSPACE puede ser reducido a él en tiempo polinómico (véase completo (complejidad)). Puede pensarse que los problemas que son PSPACE-completos son los más difíciles de resolver en la clase PSPACE. Se sospecha ampliamente que estos problemas pueden estar fuera de las conocidas clases de complejidad P y NP, pero no es un hecho que haya sido demostrado. Sin embargo se tiene la certeza de que están fuera de NC.
rdf:langString
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. Problems known to be PSPACE-complete include determining properties of regular expressions and context-sensitive grammars, determining the truth of quantified Boolean formulas, step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games.
rdf:langString
계산 복잡도 이론에서 PSPACE-완전은 복잡도 종류이다. 판정 문제는 PSPACE에 들어 있고, 모든 PSPACE 문제가 이 문제로 될 수 있으면 PSPACE-완전이 된다. PSPACE-완전에 드는 문제는 PSPACE에서 가장 어려운 문제로 볼 수 있다. 이 문제들은 P나 NP의 범위 바깥에 있을 것으로 보이지만, 아직 증명되지는 않았다. PSPACE-완전이 NC 바깥에 있다는 것은 증명되었다. NP-완전에 들어간다고 밝혀진 첫 문제는 충족 가능성 문제(SAT)이다. 논리식이 참이 되도록 변수값을 할당할 수 있는지를 묻는 문제이다. 예를 들어, 다음 논리식을 참이 되게 할 수 있는지를 물을 수 있다. SAT 문제는 문제로 일반화할 수 있다. 이 문제는 가장 기본이 되는 PSPACE-완전 문제이다. 이 문제의 인스턴스는 전칭기호를 허용한다는 점을 빼면 SAT하고 비슷하다. NP-완전 문제는 전형적인 퍼즐과 닮았다는 점을 주목할 필요가 있다. 전형적인 퍼즐은 문제를 풀기 위해 값을 끼워맞출 방법이 있는지를 묻는다. PSPACE-완전 문제는 게임을 닮았다. 게임은 상대방이 할 수 있는 모든 이동에 대해, 내가 어떤 이동을 할 수 있는지, 내가 이기기 위해 어떤 이동을 할 수 있는지를 묻는다. 이 질문은 존재기호나 전칭기호를 대신한다. 수많은 퍼즐이 NP-완전이고, 수많은 게임이 PSPACE-완전인 것은 놀라운 일이 아니다. PSPACE-완전에 들어가는 게임(n × n 말판에서 할 수 있도록 일반화한 것)으로는 , 리버시, 솔리테어 게임인 러시아워, 마종, 소코반, 들이 있다. 일반화한 다른 게임으로 바둑, 체스, 체커는 에 들어간다. 완벽한 두 사람이 한다면 게임은 매우 길어질 수 있기 때문에 PSPACE에 들어갈 것으로 보이지 않는다. PSPACE-완전의 정의는 점근 복잡도에 기반하고 있다. 크기 n인 문제를 푸는 데 걸리는 시간은 n이 커짐에 따라 한없이 늘어나는 한계 안에 있다. 이는 8 × 8 말판에서 하는 체커 같은 게임은 절대로 PSPACE-완전일 수 없다는 뜻이다. (사실, 아주 큰 을 쓰면 상수 시간에 풀 수 있다.) 이 때문에 게임을 n × n 말판으로 일반화하여 다룬다. 체스 같은 몇몇 경우에는 이러한 확장은 인위적이고 주관적이기도 하다. 다른 PSPACE-완전 문제로는 주어진 문자열이 으로 정의한 어떤 언어에 들어가는지를 판정하는 문제가 있다.
rdf:langString
Em teoria da complexidade computacional, um problema de decisão é PSPACE-completo se pertence à classe de complexidade PSPACE e todos os problemas em PSPACE podem ser reduzidos a ele em tempo polinomial. Os problemas PSPACE-completos podem ser vistos como os problemas mais difíceis em PSPACE, porque uma solução para qualquer problema PSPACE-completo pode ser facilmente utilizada para resolver qualquer outro problema em PSPACE. Em geral, acredita-se que tais problemas não pertencem às famosas classes de complexidade P e NP, mas isso ainda é desconhecido. Sabe-se que eles estão fora da pequena classe de problemas NC, já que NC está contido em PolyL = DSPACE((log n)O(1))), que está estritamente contido em PSPACE pelo teorema da hierarquia de espaço.
xsd:nonNegativeInteger
13301