P (complexity) (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | في علم التعقيد الحسابي الصنف P هو مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج قطعية بوقت بلونومي، لهذا الصنف من المسائل اهمية بالغة في علم الحاسوب والرياضيات إذ يُنظر اليها على انها مجموعة المسائل التي يمكن تطبيقها بشكل عملي معنى الكلام: هذه المجموعة من المسائل يمكن حلها بواسطة الحاسوب المعروف وذلك لان الات تيورنج عبارة عن محاكاة للحاسوب فهو النموذج الرياضي له وقد تحوي هذه المجموعة مسائل غير قابلة للتطبيق في الواقع لان كمية الخطوات بولونومي ولكن قد يفوق القدرة الحسابية للحاسوب مثلا: مسالة وقت حلها ، هذه المسالة غير عملية بالنسبة للحاسوب ولا يمكن تنفيذها أبدًا! حتى ولو كانت كمية المدخلات 2! يتجلى من هذا انه ليس كل ما كان بولونومي يكون حله عملي. لهذا الصنف اهمية بالغة في علم الحاسوب والرياضيات التطبيقية ويرجع ذلك لكثرة ارتباطه بمسائل للوهلة الأولى لا تبدوا انها متعلقة بها ولكن في الحقيقة يوجد رابط غير مباشر. مثل: البرهان الحسابي وكتابة البراهين العلمية والسؤال الذي حير العلماء لفترة طويلة هو هل يمكن كتابة أو إنتاج برهان بواسطة حاسوب؟ وكما يتبين لك فان لهذا السؤال من الاهمية بمكان وإذا ما تبيين اننا يمكن للحاسوب إنتاج البراهين الرياضية العلمية فما نفع علماء الرياضيات؟! وإذا كان ذلك ممكنا فهل توجد طريقة لكتابة البرهان الأقصر؟ هذا جانب واحد من ارتباط هذا الصنف بالرياضيات التطبيقية والعلاقة بينهما اوسع مما ذكرت بكثير. جانب اخر لهذا الصنف وهو نظرية التعقيد الحسابي وهي ما محصلته تقول: هل هناك تعقيد حسابي؟ بمعنى: هل لبنية المسالة علاقة بالوقت المطلوب لحلها؟ هذا السؤال قد يبدو بسيطا ولكن في حقيقته معقد جدا وهو حدسية من الحدسيات التي يوليها العلم اهتماما بالغا وصيغة هذا الحدسية هي: NP=P ? وعلى بساطتها فهي معقدة والرياضيات المطلوبة لاكتشاف الجواب قد لاتكون متوفرة بعد ما يجعلها من أكثر المسائل تعقيدا في زماننا. ولهذا الصنف اهمية من جانب اخر وهو من جانب عالم الصناعات وتطوير الخوارزميات والاقتصاد وغيرها من المجالات المتعلقة. (ar) 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. (ca) 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). (cs) 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. (eo) 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. Eine Verallgemeinerung von P ist die Klasse NP. Die Probleme aus NP sind zwar ebenfalls in Polynomialzeit entscheidbar, jedoch wird hierfür ein nicht realisierbares, nämlich nichtdeterministisches Maschinenmodell eingesetzt. P ist sicher eine Teilmenge von NP. Es gehört jedoch zu den wichtigsten ungelösten Fragen der theoretischen Informatik, ob P = NP gilt (siehe auch P-NP-Problem). P ist unter Komplementbildung abgeschlossen. (de) En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor o igual 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 P. La tesis de Cobham postula que la clase P es la que tiene los problemas tratables más grandes, es decir, los problemas de gran tamaño que se pueden calcular de forma eficiente con un ordenador. 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. Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos , los lineales , los cuadráticos , los cúbicos , etc. (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. Les problèmes dans P sont considérés comme « faisables » (feasible en anglais), faciles à résoudre (dans le sens où on peut le faire relativement rapidement). C'est la thèse de Cobham émise par le scientifique américain Alan Cobham. René Lalement attribue cette thèse à Cook. La classe P est incluse dans la classe NP, conduisant à l'un des grands problèmes ouverts de la théorie de la complexité, à savoir : P est-il égal à NP ? (fr) 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. (en) 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. (it) 計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。 (ja) P(PTIME 또는 (nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다. 선형 계획 제품, 최대공약수 문제 등이 P에 포함되며, 2002년에는 주어진 숫자가 소수인지 판별하는 문제도 P에 속한다는 것이 증명되었다 보통 P는 효율적으로 다룰 수 있는 문제의 집합으로 생각되지만, 나 BPP와 같은 더 큰 집합의 문제도 효율적으로 다룰 수 있다. 또한 P에 속한다고 해서 항상 실용적인 것은 아닌데, 이론적으로는 다항 시간 내에 풀 수 있지만 실제 걸리는 시간이 비효율적일 가능성도 충분히 있기 때문이다. (ko) 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? Trudno znaleźć rozwiązanie tego zagadnienia w czasie wielomianowym. Nasuwający się algorytm sprawdzenia wszystkich możliwych podzbiorów ma złożoność wykładniczą ze względu na liczebność zbioru. Nie wiadomo zatem czy problem ten jest klasy P. Na pewno natomiast uzyskawszy z zewnątrz kandydata na rozwiązanie (np. {-2,6,-3,10,-11}) można w liniowym (czyli również wielomianowym) czasie sprawdzić czy sumuje się do zera. Jest to zatem problem NP. Każdy problem P jest NP, jednak nie wiadomo czy istnieje problem NP niebędący P. Jest to jedno z wielkich nierozwiązanych dotychczas zagadnień informatyki. (pl) 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. (nl) 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. (pt) В теории алгоритмов классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов. (ru) Клас складності P (англ. Complexity class P) — клас задач, що можна розв'язати алгоритмами з поліноміальним часом. (uk) 在計算複雜度理論中，P（polynomial time class）是在複雜度類別問題中可於確定型圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以「有效率地解決」或「溫馴」的可計算型問題，就算指數級非常高也可以算作「溫馴」，例如RP與BPP問題。當然P類別存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問題 (zh) |
| dbo:wikiPageID | 658550 (xsd:integer) |
| dbo:wikiPageLength | 13411 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1113888801 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Rule_of_thumb dbr:Memory_space_(computational_resource) dbr:NP_(complexity) dbr:Nonconstructive_proof dbr:Bounded-error_probabilistic_polynomial dbr:Homomorphism dbr:DTIME dbr:Decision_problem dbr:Descriptive_Complexity dbr:Dexter_Kozen dbr:Introduction_to_Algorithms dbr:Thomas_H._Cormen dbr:Robertson–Seymour_theorem dbr:Concatenation dbr:Clifford_Stein dbr:Co-NP dbr:L_(complexity) dbr:Logarithm dbr:Complement_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Function_problem dbr:Henry_Cabourn_Pocklington dbr:Sparse_language dbr:P/poly dbr:Least_fixed_point dbr:Linear_programming dbr:P-complete dbr:Alan_Cobham_(mathematician) dbr:EXPTIME dbr:Alternating_Turing_machine dbr:First-order_logic dbr:Non-deterministic_Turing_machine dbr:PSPACE dbr:Formal_language dbr:Reachability dbr:2-satisfiability dbc:Complexity_classes dbr:Intersection_(set_theory) dbr:Jack_Edmonds dbr:Prime_number dbr:Advice_(complexity) dbr:Charles_E._Leiserson dbr:Cobham's_thesis dbr:Tractable_problem dbr:Boolean_circuit dbr:Polynomial dbr:Polynomial_hierarchy dbr:St-connectivity dbr:Circuit_complexity dbr:Polynomial_time dbr:FO(LFP) dbr:Maximum_matching dbr:Kleene_closure dbr:Range_concatenation_grammars dbr:Undecidable_problem dbr:Union_(set_theory) dbr:FP_(complexity) dbr:Low_(complexity) dbr:Random_access dbr:P_versus_NP_problem dbr:Forbidden_minor dbr:Descriptive_complexity dbr:Deterministic_Turing_machine dbr:Computation_time dbr:Ronald_L._Rivest dbr:Mitsunori_Ogihara |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Reflist dbt:Short_description dbt:Isbn dbt:ComplexityClasses dbt:CZoo |
| dct:subject | dbc:Complexity_classes |
| rdf:type | yago:WikicatControlled-accessHighways yago:Artifact100021939 yago:Highway103519981 yago:Object100002684 yago:PhysicalEntity100001930 yago:YagoGeoEntity yago:YagoPermanentlyLocatedEntity yago:Road104096066 yago:Way104564698 yago:Whole100003553 |
| 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. (ca) 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). (cs) 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. (eo) 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. (en) 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. (it) 計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。 (ja) P(PTIME 또는 (nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다. 선형 계획 제품, 최대공약수 문제 등이 P에 포함되며, 2002년에는 주어진 숫자가 소수인지 판별하는 문제도 P에 속한다는 것이 증명되었다 보통 P는 효율적으로 다룰 수 있는 문제의 집합으로 생각되지만, 나 BPP와 같은 더 큰 집합의 문제도 효율적으로 다룰 수 있다. 또한 P에 속한다고 해서 항상 실용적인 것은 아닌데, 이론적으로는 다항 시간 내에 풀 수 있지만 실제 걸리는 시간이 비효율적일 가능성도 충분히 있기 때문이다. (ko) 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. (nl) 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. (pt) В теории алгоритмов классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов. (ru) Клас складності P (англ. Complexity class P) — клас задач, що можна розв'язати алгоритмами з поліноміальним часом. (uk) 在計算複雜度理論中，P（polynomial time class）是在複雜度類別問題中可於確定型圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以「有效率地解決」或「溫馴」的可計算型問題，就算指數級非常高也可以算作「溫馴」，例如RP與BPP問題。當然P類別存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問題 (zh) في علم التعقيد الحسابي الصنف P هو مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج قطعية بوقت بلونومي، لهذا الصنف من المسائل اهمية بالغة في علم الحاسوب والرياضيات إذ يُنظر اليها على انها مجموعة المسائل التي يمكن تطبيقها بشكل عملي معنى الكلام: هذه المجموعة من المسائل يمكن حلها بواسطة الحاسوب المعروف وذلك لان الات تيورنج عبارة عن محاكاة للحاسوب فهو النموذج الرياضي له وقد تحوي هذه المجموعة مسائل غير قابلة للتطبيق في الواقع لان كمية الخطوات بولونومي ولكن قد يفوق القدرة الحسابية للحاسوب مثلا: يتجلى من هذا انه ليس كل ما كان بولونومي يكون حله عملي. (ar) 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. (de) En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor o igual 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 P. La tesis de Cobham postula que la clase P es la que tiene los problemas tratables más grandes, es decir, los problemas de gran tamaño que se pueden calcular de forma eficiente con un ordenador. (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. (fr) 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? (pl) |
| rdfs:label | كثير حدود (تعقيد) (ar) P (complexitat) (ca) P (třída složitosti) (cs) P (Komplexitätsklasse) (de) P (komplikeco) (eo) P (clase de complejidad) (es) P (complessità) (it) P (complexité) (fr) P (복잡도) (ko) P (計算複雑性理論) (ja) P (complexity) (en) P (complexiteitsklasse) (nl) Problem P (pl) P (complexidade) (pt) Класс P (ru) Клас складності P (uk) P (複雜度) (zh) |
| owl:sameAs | freebase:P (complexity) yago-res:P (complexity) wikidata:P (complexity) dbpedia-ar:P (complexity) dbpedia-ca:P (complexity) dbpedia-cs:P (complexity) dbpedia-de:P (complexity) dbpedia-eo:P (complexity) dbpedia-es:P (complexity) dbpedia-fa:P (complexity) dbpedia-fi:P (complexity) dbpedia-fr:P (complexity) dbpedia-he:P (complexity) dbpedia-it:P (complexity) dbpedia-ja:P (complexity) dbpedia-ko:P (complexity) dbpedia-nl:P (complexity) dbpedia-nn:P (complexity) dbpedia-no:P (complexity) dbpedia-pl:P (complexity) dbpedia-pt:P (complexity) dbpedia-ro:P (complexity) dbpedia-ru:P (complexity) dbpedia-sr:P (complexity) dbpedia-th:P (complexity) dbpedia-tr:P (complexity) dbpedia-uk:P (complexity) dbpedia-vi:P (complexity) dbpedia-zh:P (complexity) https://global.dbpedia.org/id/4zyvp |
| prov:wasDerivedFrom | wikipedia-en:P_(complexity)?oldid=1113888801&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:P_(complexity) |
| is dbo:knownFor of | dbr:Alan_Cobham_(mathematician) |
| is dbo:wikiPageDisambiguates of | dbr:P_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Nonuniform_polynomial-time dbr:Nonuniform_polynomial_time dbr:AL_(complexity) dbr:P-hard dbr:PTIME dbr:P_(class) dbr:P_(complexity_class) dbr:Complexity_class_P |
| is dbo:wikiPageWikiLink of | dbr:Proof_complexity dbr:Quantum_complexity_theory dbr:List_of_complexity_classes dbr:NP_(complexity) dbr:Parity_game dbr:Primality_test dbr:Nonuniform_polynomial-time dbr:Nonuniform_polynomial_time dbr:Algorithm dbr:DTIME dbr:Vadalog dbr:Decomposition_method_(constraint_satisfaction) dbr:Descriptive_Complexity dbr:Descriptive_complexity_theory dbr:Deutsch–Jozsa_algorithm dbr:EXPSPACE dbr:Integer_circuit dbr:Interactive_proof_system dbr:Intersection_type_discipline dbr:Quantum_computing dbr:Schulze_method dbr:Universal_algebra dbr:PSPACE-complete dbr:Post's_lattice dbr:Simon's_problem dbr:Whitehead's_algorithm dbr:♯P dbr:♯P-complete dbr:Cryptography dbr:Geometric_complexity_theory dbr:P_(disambiguation) dbr:Non-constructive_algorithm_existence_proofs dbr:Valiant–Vazirani_theorem dbr:Schaefer's_dichotomy_theorem dbr:QMA dbr:Quantum_algorithm dbr:Church–Turing_thesis dbr:Co-NP dbr:Greatest_common_divisor dbr:NC_(complexity) dbr:NL_(complexity) dbr:Constraint_satisfaction_problem dbr:L_(complexity) dbr:Closed-world_assumption dbr:Complexity dbr:Complexity_class dbr:Complexity_of_constraint_satisfaction dbr:Computational_complexity_theory dbr:Computational_problem dbr:Horn-satisfiability dbr:PH_(complexity) dbr:PLS_(complexity) dbr:P_class dbr:Padding_argument dbr:Probabilistically_checkable_proof dbr:Sparse_language dbr:Succinct_game dbr:Many-one_reduction dbr:P/poly dbr:BPP_(complexity) dbr:BQP dbr:Time_complexity dbr:Travelling_Salesman_(2012_film) dbr:Lattice_reduction dbr:Least_fixed_point dbr:Linear_programming dbr:Local_consistency dbr:Log-space_reduction dbr:Polynomial-time_reduction dbr:P-complete dbr:Path_cover dbr:Resource_bounded_measure dbr:Alan_Cobham_(mathematician) dbr:DFA_minimization dbr:EXPTIME dbr:Alternating_Turing_machine dbr:PSPACE dbr:Cem_Say dbr:Digi-Comp_II dbr:Digraph_realization_problem dbr:Discrete_mathematics dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Reduction_(complexity) dbr:2-EXPTIME dbr:AL_(complexity) dbr:Jack_Edmonds dbr:Bipartite_realization_problem dbr:Co-NP-complete dbr:Cobham's_thesis dbr:Holographic_algorithm dbr:ZPP_(complexity) dbr:Average-case_complexity dbr:Boolean_circuit dbr:Boolean_satisfiability_problem dbr:CC_(complexity) dbr:Polynomial_hierarchy dbr:St-connectivity dbr:Circuit_Value_Problem dbr:Circuit_complexity dbr:Circuits_over_sets_of_natural_numbers dbr:Minimum_spanning_tree dbr:RP_(complexity) dbr:Randomized_algorithm dbr:SC_(complexity) dbr:UP_(complexity) dbr:Vijay_Vazirani dbr:FKT_algorithm dbr:FP_(complexity) dbr:Low_(complexity) dbr:Exact_quantum_polynomial_time dbr:Finite_model_theory dbr:First-order_reduction dbr:Fixed-point_logic dbr:NEXPTIME dbr:NFA_minimization dbr:NP-hardness dbr:NP-intermediate dbr:NL-complete dbr:Multitape_Turing_machine dbr:PolyL dbr:Time_hierarchy_theorem dbr:Turing_reduction dbr:Ultrafinitism dbr:Set_packing dbr:Savitch's_theorem dbr:P_versus_NP_problem dbr:Unknotting_problem dbr:Sipser–Lautemann_theorem dbr:Structural_complexity_theory dbr:Space_complexity dbr:P-hard dbr:PTIME dbr:P_(class) dbr:P_(complexity_class) dbr:Complexity_class_P |
| is foaf:primaryTopic of | wikipedia-en:P_(complexity) |