About: P (complexity)

Property	Value
dbo:description	classe di complessità (it) třída složitosti (cs) complexiteitsklasse (nl) clase de complejidad computacional de problemas resolubles por una Máquina de Turing determinista en tiempo polinomial (es) in der Komplexitätstheorie eine Komplexitätsklasse (de) klaso da decidoproblemoj solveblaj per determina Turing-maŝino en polinoma tempo (eo) classe de complexitat computacional (ca) classe de complexité des algorithmes (fr) computational complexity class of problems (en) yksi ongelmanratkaisutavan luokista laskennan vaativuusteoriassa (fi) множество задач, для которых существуют алгоритмы решения, время работы которых полиномиально зависит от размера входных данных (ru) 計算量のクラスのひとつ (ja) 多項式時間內確定性圖靈機可解決的計算複雜度問題。 (zh)
dbo:thumbnail	wiki-commons:Special:FilePath/Complexity_subsets_pspace.svg?width=300
dbo:wikiPageWikiLink	dbr:Introduction_to_Algorithms dbr:P_versus_NP_problem dbr:Random_access dbr:Prime_number dbr:Clifford_Stein dbr:Computation_time dbr:Logarithm dbr:First-order_logic dbr:Concatenation dbr:NP_(complexity) dbr:Complement_(complexity) dbr:Homomorphism dbr:Linear_programming dbr:PSPACE dbr:Reachability dbr:St-connectivity dbr:Polynomial_hierarchy dbr:EXPTIME dbr:Dexter_Kozen dbr:DTIME dbr:Formal_language dbr:Rule_of_thumb dbr:Co-NP dbr:FP_(complexity) dbr:Boolean_circuit dbr:Circuit_complexity dbr:L_(complexity) dbr:Thomas_H._Cormen dbr:Least_fixed_point dbr:Cobham's_thesis dbr:Charles_E._Leiserson dbr:Jack_Edmonds dbr:Intersection_(set_theory) dbr:Computational_complexity_theory dbr:Robertson–Seymour_theorem dbr:Bounded-error_probabilistic_polynomial dbr:Polynomial dbr:Complexity_class dbr:Function_problem dbr:P-complete dbr:Sparse_language dbr:Alternating_Turing_machine dbr:Undecidable_problem dbr:P/poly dbr:Union_(set_theory) dbr:Advice_(complexity) dbc:Complexity_classes dbr:Henry_Cabourn_Pocklington dbr:2-satisfiability dbr:Memory_space_(computational_resource) dbr:Range_concatenation_grammars dbr:Decision_problem dbr:Low_(complexity) dbr:Alan_Cobham_(mathematician) dbr:Polynomial_time dbr:Descriptive_Complexity dbr:Ronald_L._Rivest dbr:Non-deterministic_Turing_machine dbr:Kleene_closure dbr:Tractable_problem dbr:Maximum_matching dbr:Mitsunori_Ogihara dbr:Descriptive_complexity dbr:Forbidden_minor dbr:FO(LFP) dbr:Deterministic_Turing_machine dbr:Nonconstructive_proof
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Reflist dbt:Cite_journal dbt:Sfn dbt:ComplexityClasses dbt:Cite_conference dbt:Isbn dbt:Short_description dbt:CZoo
dct:subject	dbc:Complexity_classes
rdfs:label	P (complexity) (en) كثير حدود (تعقيد) (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 (計算複雑性理論) (ja) P (complexité) (fr) P (복잡도) (ko) P (complexiteitsklasse) (nl) Problem P (pl) P (complexidade) (pt) Клас складності P (uk) Класс P (ru) P (複雜度) (zh)
owl:sameAs	freebase:P (complexity) yago-res:P (complexity) wikidata:P (complexity) dbpedia-it:P (complexity) dbpedia-nl:P (complexity) dbpedia-de:P (complexity) dbpedia-fr:P (complexity) dbpedia-tr:P (complexity) dbpedia-zh:P (complexity) dbpedia-ja:P (complexity) dbpedia-pt:P (complexity) dbpedia-he:P (complexity) dbpedia-ro:P (complexity) dbpedia-es:P (complexity) dbpedia-fa:P (complexity) dbpedia-ru:P (complexity) dbpedia-vi:P (complexity) dbpedia-pl:P (complexity) dbpedia-ko:P (complexity) dbpedia-ca:P (complexity) dbpedia-ar:P (complexity) dbpedia-cs:P (complexity) dbpedia-eo:P (complexity) dbpedia-fi:P (complexity) dbpedia-nn:P (complexity) dbpedia-no:P (complexity) dbpedia-sr:P (complexity) dbpedia-th:P (complexity) dbpedia-uk:P (complexity) dbpedia-global:P (complexity)
prov:wasDerivedFrom	wikipedia-en:P_(complexity)?oldid=1293552897&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Randomised_Complexity_Classes_2.svg wiki-commons:Special:FilePath/Complexity-classes-polynomial.svg wiki-commons:Special:FilePath/Complexity_subsets_pspace.svg
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:AL_(complexity) dbr:PTIME dbr:P_(class) dbr:P_(complexity_class) dbr:P-hard dbr:Complexity_class_P dbr:Nonuniform_polynomial-time dbr:Nonuniform_polynomial_time
is dbo:wikiPageWikiLink of	dbr:BPP_(complexity) dbr:Co-NP-complete dbr:EXPSPACE dbr:NC_(complexity) dbr:Polynomial-time_reduction dbr:Space_complexity dbr:Fixed-point_logic dbr:NL_(complexity) dbr:Minimum_spanning_tree dbr:P_versus_NP_problem dbr:Complexity dbr:NEXPTIME dbr:Constraint_satisfaction_problem dbr:NP-intermediate dbr:Deutsch–Jozsa_algorithm dbr:Discrete_mathematics dbr:NP_(complexity) dbr:Parity_game dbr:Graph_isomorphism dbr:Log-space_reduction dbr:Linear_programming dbr:PSPACE dbr:St-connectivity dbr:Multitape_Turing_machine dbr:Polynomial_hierarchy dbr:EXPTIME dbr:Many-one_reduction dbr:Digi-Comp_II dbr:NL-complete dbr:2-EXPTIME dbr:Post's_lattice dbr:Greatest_common_divisor dbr:DTIME dbr:Local_consistency dbr:Cryptography dbr:Schulze_method dbr:Church–Turing_thesis dbr:Descriptive_complexity_theory dbr:QMA dbr:FKT_algorithm dbr:Integer_circuit dbr:♯P dbr:Co-NP dbr:Savitch's_theorem dbr:FP_(complexity) dbr:Boolean_circuit dbr:Circuit_complexity dbr:Probabilistically_checkable_proof dbr:♯P-complete dbr:L_(complexity) dbr:RP_(complexity) dbr:Proof_complexity dbr:Algorithm dbr:Quantum_computing dbr:Horn-satisfiability dbr:Least_fixed_point dbr:Cobham's_thesis dbr:Jack_Edmonds dbr:Vijay_Vazirani dbr:Computational_complexity_theory dbr:Quantum_algorithm dbr:Succinct_game dbr:Boolean_satisfiability_problem dbr:ZPP_(complexity) dbr:Circuit_Value_Problem dbr:Complexity_class dbr:List_of_complexity_classes dbr:P-complete dbr:PSPACE-complete dbr:Reduction_(complexity) dbr:UP_(complexity) dbr:DFA_minimization dbr:PolyL dbr:Sparse_language dbr:Travelling_Salesman_(2012_film) dbr:Alternating_Turing_machine dbr:BQP dbr:Set_packing dbr:Universal_algebra dbr:Interactive_proof_system dbr:Graph_isomorphism_problem dbr:Turing_reduction dbr:CC_(complexity) dbr:Average-case_complexity dbr:Structural_complexity_theory dbr:Schaefer's_dichotomy_theorem dbr:P/poly dbr:PLS_(complexity) dbr:P_class dbr:Padding_argument dbr:Sipser–Lautemann_theorem dbr:NP-hardness dbr:Time_complexity dbr:Computational_problem dbr:Finite_model_theory dbr:First-order_reduction dbr:Valiant–Vazirani_theorem dbr:Closed-world_assumption dbr:Decomposition_method_(constraint_satisfaction) dbr:Time_hierarchy_theorem dbr:P_(disambiguation) dbr:Randomized_algorithm dbr:Primality_test dbr:Circuits_over_sets_of_natural_numbers dbr:Complexity_of_constraint_satisfaction dbr:Simon's_problem dbr:Holographic_algorithm dbr:Exact_quantum_polynomial_time dbr:Ultrafinitism dbr:Low_(complexity) dbr:Lattice_reduction dbr:Non-constructive_algorithm_existence_proofs dbr:Resource_bounded_measure dbr:AL_(complexity) dbr:Quantum_complexity_theory dbr:NFA_minimization dbr:SC_(complexity) dbr:Unknotting_problem dbr:Bipartite_realization_problem dbr:Digraph_realization_problem dbr:Alan_Cobham_(mathematician) dbr:Whitehead's_algorithm dbr:Intersection_type_discipline dbr:Vadalog dbr:Geometric_complexity_theory dbr:Path_cover dbr:Cem_Say dbr:Descriptive_Complexity dbr:PH_(complexity) dbr:PTIME dbr:P_(class) dbr:P_(complexity_class) dbr:P-hard dbr:Complexity_class_P dbr:Nonuniform_polynomial-time dbr:Nonuniform_polynomial_time
is foaf:primaryTopic of	wikipedia-en:P_(complexity)