e/P (complexity)

New Query

Information
has glosseng: In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
lexicalizationeng: p
instance ofe/Complexity class
Meaning
Catalan
has glosscat: 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.
lexicalizationcat: p
Czech
has glossces: V teorii složitosti je P jednou z nejzákladnějších tříd složitosti. Obsahuje všechny problémy řešitelné pomocí deterministického Turingova stroje v polynomiálním množství času.
lexicalizationces: p
German
has glossdeu: In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die 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.
lexicalizationdeu: P
Esperanto
has glossepo: En komputa komplikteorio, P estas komplikeca klaso de decidaj problemoj kiuj povas esti solvitaj per determinisma maŝino de Turing en polinoma tempo.
lexicalizationepo: p
Finnish
has glossfin: P (polynomial) on laskennan vaativuusteoriassa vaativuusluokka, johon kuuluvat ongelmat voidaan ratkaista deterministisellä Turingin koneella polynomisessa ajassa, eli tehokkaasti. Polynominen aika tarkoittaa sitä, että ratkaisuun tarvittavien laskutoimenpiteiden määrä on O(na), missä a on vakio. Vaativuusluokkaan P kuuluvia ongelmia ovat muun muassa suurimman yhteisen tekijän etsiminen tai luvun verifointi alkuluvuksi.
lexicalizationfin: p
Hebrew
has glossheb: בתחום הסיבוכיות במדעי המחשב, P היא מחלקת סיבוכיות המכילה את כל בעיות ההכרעה אשר ניתנות לפתרון באופן יעיל, דהיינו בזמן ריצה פולינומי.
lexicalizationheb: P
Italian
lexicalizationita: p
Japanese
has glossjpn: 計算複雑性理論におけるPとは判定問題の複雑性クラスの一つであり、Polynomial time の略である。
lexicalizationjpn: P
Korean
has glosskor: P는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다. 선형 계획 문제, 최대공약수 문제 등이 P에 포함되며, 2002년에는 주어진 숫자가 소수인지 판별하는 문제도 P에 속한다는 것이 증명되었다 .
lexicalizationkor: P
Dutch
has glossnld: In de complexiteitstheorie is P, ook bekend als PTIME en DTIME(nO(1)), een complexiteitsklasse 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.
lexicalizationnld: p
Polish
has glosspol: Problem P (ang. deterministic polynomial - deterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.
lexicalizationpol: Problem P
Russian
has glossrus: В теории алгоритмов классом P (от англ. polynomial) называют множество алгоритмов, время работы которых не слишком сильно зависит от размера входных данных (не превосходит многочлена от размера данных). Алгоритмы, принадлежащие классу P, считаются быстрыми. Класс P включён в более широкие классы сложности алгоритмов.
lexicalizationrus: класс P
Castilian
has glossspa: Introducción Los recursos comúnmente estudiados en complejidad computacional son: – El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.
lexicalizationspa: p
Thai
has glosstha: ในเชิงของ ทฤษฎีความซับซ้อนในการคำนวณ พี เป็นกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถหาคำตอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต (polynomial time)
lexicalizationtha: พี
Turkish
has glosstur: P, çokterimli zamanda (belirlenimli Turing Makinesi ile) çözülebilen karar problemlerini içeren karmaşıklık sınıfıdır. P sınıfı pek çok doğal problemi içerse de bazı önemli problemlerin (bk. NP) P içerisine girip girmediği bilinmemektedir.
lexicalizationtur: p
Ukrainian
has glossukr: Клас складності P — клас задач, що можна розв'язати алгоритмами з поліноміальним часом.
lexicalizationukr: Клас складності P
Chinese
has glosszho: 在計算複雜度理論中,P 是在複雜度類問題中可於決定性圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。
lexicalizationzho: P
Media
media:imgComplexity subsets pspace.svg
media:imgGraficoADA.jpg
media:imgMatrizADA.gif

Query

Word: (case sensitive)
Language: (ISO 639-3 code, e.g. "eng" for English)


Lexvo © 2008-2025 Gerard de Melo.   Contact   Legal Information / Imprint