About: P (complexity)     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Highway103519981, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FP_%28complexity%29

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.

AttributesValues
rdf:type
rdfs:label
  • كثير حدود (تعقيد)
  • P (complexitat)
  • P (třída složitosti)
  • P (Komplexitätsklasse)
  • P (komplikeco)
  • P (complexity)
  • P (clase de complejidad)
  • P (complexité)
  • P (計算複雑性理論)
  • P (complessità)
  • P (복잡도)
  • P (complexiteitsklasse)
  • Problem P
  • P (complexidade)
  • Класс P
  • Клас складності P
  • P (複雜度)
rdfs:comment
  • En Teoria de complexitat computacional, P és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing determinista usant una quantitat de temps de computació polinòmic (temps polinòmic). Es considera P com la classe de problemes que computacionalment són "eficientment resolubles" o "tractables", tot i que hi ha classes majors que es poden considerar tractables com RP o BPP. A més, hi ha problemes dins de P que són intractables en termes pràctics: per exemple, poden requerir n1000000 operacions.
  • V teorii složitosti je P jednou z nejzákladnějších . Obsahuje všechny problémy řešitelné pomocí deterministického Turingova stroje v polynomiálním čase. P je obvykle považována za třídu problémů, které jsou efektivně řešitelné (existují ale i další třídy považované za efektivně řešitelné, jako RP a BPP), přesto není v této třídě problém najít i efektivně neřešitelné problémy (se složitostí například N1000000).
  • En , P estas de kiuj povas esti solvitaj per en polinoma tempo. P estas ofte konsiderata kiel klaso de komputaj problemoj kiu estas sufiĉe rapide solveblaj, kvankam estas eble pli grandaj klasoj ankaŭ kiuj estas konsiderataj kiel sufiĉe rapide solveblaj - RP kaj BPP. Ankaŭ, ekzistas problemoj en P kiuj estas tro malfacilaj en praktiko, ekzemple, se iu postulas almenaŭ n100000 operaciojn.
  • In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.
  • Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o (nO(1)), è una delle più importanti classi di complessità. Contiene tutti i problemi decisionali che possono essere risolti da una macchina di Turing deterministica usando una quantità di , o tempo polinomiale. La asserisce che P è la classe di problemi computazionali che sono "risolvibili efficientemente" o "trattabili"; in pratica, qualche problema che non si sa essere in P ha soluzioni pratiche, e qualche problema in P non ne ha.
  • 計算量理論におけるPとは多項式時間(polynomial time)で解ける判定問題の集合である。
  • P(PTIME 또는 (nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다. 선형 계획 제품, 최대공약수 문제 등이 P에 포함되며, 2002년에는 주어진 숫자가 소수인지 판별하는 문제도 P에 속한다는 것이 증명되었다 보통 P는 효율적으로 다룰 수 있는 문제의 집합으로 생각되지만, 나 BPP와 같은 더 큰 집합의 문제도 효율적으로 다룰 수 있다. 또한 P에 속한다고 해서 항상 실용적인 것은 아닌데, 이론적으로는 다항 시간 내에 풀 수 있지만 실제 걸리는 시간이 비효율적일 가능성도 충분히 있기 때문이다.
  • In de complexiteitstheorie is P, ook bekend als PTIME en DTIME(nO(1)), een die alle beslissingsproblemen bevat die in polynomiale tijd opgelost kunnen worden door een deterministische turingmachine. Als vuistregel hanteert men dat de problemen die tot de complexiteitsklasse P behoren "efficiënt" oplosbaar zijn; er bestaan uitzonderingen hierop maar deze regel geldt over het algemeen wel. Enkele problemen die tot P behoren zijn het testen of een getal een priemgetal is, vraagstukken op het gebied van lineair programmeren en het berekenen van de grootste gemene deler.
  • Na teoria da complexidade computacional, P é o acrônimo em inglês para Tempo polinomial determinístico (Deterministic Polynomial time) que denota o conjunto de problemas que podem ser resolvidos em por uma máquina de Turing determinística.Qualquer problema deste conjunto pode ser resolvido por um algoritmo com tempo de execução O(n^{k}), (com k constante). Podemos ter a classe P como a classe de problemas que são solúveis para um computador real. Embora esta definição não seja exata, é uma boa aproximação para servir de base para nosso estudo.
  • В теории алгоритмов классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов.
  • Клас складності P (англ. Complexity class P) — клас задач, що можна розв'язати алгоритмами з поліноміальним часом.
  • 在計算複雜度理論中,P(polynomial time class)是在複雜度類別問題中可於決定性圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。 P通常表示那類可以「有效率地解決」或「溫馴」的可計算型問題,就算指數級非常高也可以算作「溫馴」,例如RP與BPP問題。當然P類別存在很多現實處理上一點也不溫馴的問題,例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問題
  • في علم التعقيد الحسابي الصنف P هو مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج قطعية بوقت بلونومي , لهذا الصنف من المسائل اهمية بالغة في علم الحاسوب والرياضيات إذ يُنظر اليها على انها مجموعة المسائل التي يمكن تطبيقها بشكل عملي معنى الكلام : هذه المجموعة من المسائل يمكن حلها بواسطة الحاسوب المعروف وذلك لان الات تيورنج عبارة عن محاكاة للحاسوب فهو النموذج الرياضي له وقد تحوي هذه المجموعة مسائل غير قابلة للتطبيق في الواقع لان كمية الخطوات بولونومي ولكن قد يفوق القدرة الحسابية للحاسوب مثلا : يتجلى من هذا انه ليس كل ما كان بولونومي يكون حله عملي .
  • In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, die alle Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der „praktisch lösbaren“ Probleme betrachtet. P ist unter Komplementbildung abgeschlossen.
  • En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico. Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por casas necesita menos de segundos, entonces el problema es resoluble en un "tiempo polinómico". De esa manera, tiempos de , o son polinómicos; pero no lo es.
  • La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial.
  • Problem P (ang. deterministic polynomial, deterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym. Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność. Przykładowy problem: Czy jakikolwiek podzbiór zadanego zbioru {-2,6,-3,72,10,-11} sumuje się do zera?
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Faceted Search & Find service v1.17_git51 as of Sep 16 2020


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3321 as of Jun 2 2021, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software