About: Complexity class

Property	Value
dbo:description	En teoria de complexitat computacional, conjunt de problemes relacionats pels recursos computacionals requerits per resoldre'ls (ca) množina problémů majících nějakou danou složitost vůči nějakému zdroji (cs) set of problems in computational complexity theory of related resource-based complexity (en) en teoría de complejidad computacional, conjunto de problemas relacionados por los recursos computacionales requeridos para resolverlos (es) Gruppen, deren Aufwand für große Eingabemengen auf ähnliche Weise anwächst (de) joukko ongelmia laskennan vaativuusteoriassa (fi) insieme di problemi di una certa complessità computazionale (it) ensemble de problèmes algorithmiques partageant une même complexité algorithmique (fr) 基於資源的複雜性相關的計算複雜性理論中的一系列問題 (zh) אוסף בעיות בעלות סיבוכיות משותפת (iw)
dbo:thumbnail	wiki-commons:Special:FilePath/Complexity_subsets_pspace.svg?width=300
dbo:wikiPageExternalLink	https://archive.org/details/computationalcom00aror http://fuuu.be/polytech/INFOF408/Introduction-To-The-Theory-Of-Computation-Michael-Sipser.pdf%7Carchive-url=https:/web.archive.org/web/20220207141236/http:/fuuu.be/polytech/INFOF408/Introduction-To-The-Theory-Of-Computation-Michael-Sipser.pdf%7Carchive-date=February http://theory.cs.princeton.edu/complexity/book.pdf https://lance.fortnow.com/papers/files/counting.pdf https://web.archive.org/web/20160416021243/https:/people.cs.umass.edu/~immerman/complexity_theory.html https://web.archive.org/web/20200617175017/https:/eccc.weizmann.ac.il/report/2017/004/download/%7Carchive-date=June https://web.archive.org/web/20210403191124/https:/www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf https://web.archive.org/web/20210506131638/https:/www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf https://web.archive.org/web/20211102102656/https:/www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf%7Carchive-date=November https://web.archive.org/web/20211129075858/https:/courses.cs.washington.edu/courses/cse431/14sp/scribes/lec16.pdf https://web.archive.org/web/20220223014316/https:/theory.cs.princeton.edu/complexity/book.pdf https://web.archive.org/web/20220521204917/https:/www.cs.princeton.edu/courses/archive/spring03/cs522/book2.ps https://web.archive.org/web/20220618022421/https:/cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.22.pdf https://web.archive.org/web/20220618222631/https:/lance.fortnow.com/papers/files/counting.pdf https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.22.pdf https://www.cs.princeton.edu/courses/archive/spring03/cs522/book2.ps https://www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf https://www.cs.utexas.edu/~ear/cs341/automatabook/AutomataTheoryBook.pdf%7Carchive-url=https:/web.archive.org/web/20220121174820/https:/www.cs.utexas.edu/~ear/cs341/automatabook/AutomataTheoryBook.pdf%7Carchive-date=January https://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf https://eccc.weizmann.ac.il/report/2017/004/ http://www.cs.umass.edu/~immerman/complexity_theory.html https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf https://complexityzoo.uwaterloo.ca/Complexity_Zoo https://courses.cs.washington.edu/courses/cse431/14sp/scribes/lec16.pdf https://web.archive.org/web/20190827233504/https:/complexityzoo.uwaterloo.ca/Complexity_Zoo
dbo:wikiPageWikiLink	dbr:Abstract_machine dbr:BPP_(complexity) dbr:PP_(complexity) dbr:EXPSPACE dbr:NC_(complexity) dbr:Polynomial-time_reduction dbr:Space_complexity dbr:List_of_undecidable_problems dbr:NL_(complexity) dbr:File:Three_input_Boolean_circuit.jpg dbr:Quantum_Turing_machine dbr:NEXPTIME dbr:Computational_model dbr:Binary_number dbr:Prime_number dbr:Regular_grammar dbr:Optimization_problem dbr:University_of_Waterloo dbr:Recursively_enumerable_language dbr:FNP_(complexity) dbr:Function_(mathematics) dbr:Mathematical_proof dbr:Set_(mathematics) dbr:NP_(complexity) dbr:Closure_(mathematics) dbr:Recursive_language dbr:Log-space_reduction dbr:PSPACE dbr:Multitape_Turing_machine dbr:Polynomial_hierarchy dbr:Parallel_algorithm dbr:Quantum_information_science dbr:EXPTIME dbr:Counting_problem_(complexity) dbr:Big_O_notation dbc:Computational_complexity_theory dbr:Computer dbr:Cryptography dbr:Church–Turing_thesis dbr:Formal_language dbr:Logical_conjunction dbr:QMA dbr:University_of_Washington dbr:Open_problem dbr:Co-NP dbr:Savitch's_theorem dbr:FP_(complexity) dbr:Computability dbr:Computability_theory dbr:Alphabet_(formal_languages) dbr:Boolean_circuit dbr:Directed_acyclic_graph dbr:Nondeterministic_Turing_machine dbr:Probabilistic_Turing_machine dbr:RP_(complexity) dbr:Algorithm dbr:Bit dbr:Byte dbc:Theoretical_computer_science dbr:Economics dbr:Linguistics dbr:AND_gate dbr:OR_gate dbr:RL_(complexity) dbr:Subset dbr:Certificate_(complexity) dbr:Complete_(complexity) dbr:David_S._Johnson dbr:Neil_Immerman dbr:Promise_problem dbr:Logical_connective dbr:Negation dbr:Statistical_physics dbr:Computational_complexity_theory dbr:Blum_axioms dbr:Sharp-P dbr:Bounded-error_probabilistic_polynomial dbr:Polynomial dbr:Context-free_grammar dbr:ZPP_(complexity) dbc:Measures_of_complexity dbr:Complexity_class dbr:Context-sensitive_grammar dbr:Function_problem dbr:List_of_complexity_classes dbr:Processor_(computing) dbr:QIP_(complexity) dbr:Space_hierarchy_theorem dbr:Approximation_algorithm dbr:Prentice_Hall dbr:BQP dbr:P_(complexity) dbr:Interactive_proof_system dbr:Undecidable_problem dbr:Logarithmic_growth dbr:P/poly dbr:Exponential_function dbr:Formal_verification dbr:Logic_gate dbr:AC_(complexity) dbr:String_(computer_science) dbr:Time_complexity dbr:Computational_problem dbr:Advice_(complexity) dbr:IP_(complexity) dbr:Time_hierarchy_theorem dbr:Natural_number dbr:Princeton_University dbr:Turing_machine dbc:Complexity_classes dbr:Planar_graph dbr:Randomized_algorithm dbr:Boolean_function dbr:Primality_test dbr:Michael_Garey dbr:Nondeterministic_algorithm dbr:Yes-no_question dbr:Decision_problem dbr:Model_of_computation dbr:Computational_complexity dbr:Deterministic dbr:BPL_(complexity) dbr:AM_(complexity) dbr:MA_(complexity) dbr:Interactive_proof_systems dbr:Recursive_set dbr:NP-complete dbr:NP-hard dbr:Polynomial_time dbr:Upper_bound dbr:NOT_gate dbr:University_of_Maryland dbr:Quantum_computer dbr:Digital_circuit dbr:One-sided_error dbr:Recursively_enumerable_set dbr:P_versus_NP dbr:File:Complexity_subsets_pspace.svg dbr:File:Decision_Problem.svg dbr:File:Difference_between_deterministic_and_Nondeterministic.svg dbr:File:DottedLine.png dbr:File:Interactive_proof_(complexity).svg dbr:File:Randomized_Complexity_Classes.svg dbr:File:SolidLine.png dbr:File:Turing_machine_2b.svg dbr:Non-uniform_computation dbr:Primality_testing dbr:Probabilistic_algorithm dbr:Simple_cycle dbr:Statistical_estimation dbr:Cook_reduction dbr:Levin_reduction dbr:Network_design dbr:Directed_path dbr:Deterministic_Turing_machine dbr:Disjunction dbr:Randomized_Logarithmic-space_Polynomial-time dbr:Randomized_computation dbr:Co-RP dbr:Karp_reduction dbr:Logarithmic_function dbr:Two-sided_error
dbp:date	2019-08-27 (xsd:date)
dbp:url	https://web.archive.org/web/20190827233504/https:/complexityzoo.uwaterloo.ca/Complexity_Zoo
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Cite_web dbt:Main dbt:Reflist dbt:Notelist dbt:Expand_section dbt:Sfn dbt:ComplexityClasses dbt:See_also dbt:Sfnp dbt:Cite_encyclopedia dbt:Mvar dbt:Main_article dbt:Snf dbt:Webarchive dbt:Efn dbt:Short_description
dct:subject	dbc:Computational_complexity_theory dbc:Theoretical_computer_science dbc:Measures_of_complexity dbc:Complexity_classes
gold:hypernym	dbr:Set
rdf:type	owl:Thing owl:Thing
rdfs:label	Complexity class (en) Komplexitätsklasse (de) Classe de complexitat (ca) قسم تعقيد (ar) Clase de complejidad (es) Classe de complexité (fr) Classe di complessità (it) 複雑性クラス (ja) 복잡도 종류 (ko) Complexiteitsgraad (nl) Klasa złożoności (pl) Classe de complexidade (pt) Komplexitetsklass (sv) Класс сложности (ru) 复杂性类 (zh)
rdfs:seeAlso	dbr:List_of_complexity_classes dbr:Reduction_(complexity)
owl:sameAs	yago-res:Complexity class freebase:Complexity class wikidata:Complexity class dbpedia-it:Complexity class dbpedia-nl:Complexity class dbpedia-de:Complexity class dbpedia-fr:Complexity class dbpedia-zh:Complexity class dbpedia-ja:Complexity class dbpedia-pt:Complexity class dbpedia-he:Complexity class dbpedia-ro:Complexity class dbpedia-es:Complexity class dbpedia-fa:Complexity class dbpedia-ru:Complexity class dbpedia-sv:Complexity class dbpedia-pl:Complexity class dbpedia-ko:Complexity class dbpedia-ca:Complexity class dbpedia-ar:Complexity class dbpedia-hr:Complexity class dbpedia-nn:Complexity class dbpedia-no:Complexity class dbpedia-sh:Complexity class dbpedia-simple:Complexity class dbpedia-sr:Complexity class dbpedia-global:Complexity class dbr:Complexity class
prov:wasDerivedFrom	wikipedia-en:Complexity_class?oldid=1295422889&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Difference_between_deterministic_and_Nondeterministic.svg wiki-commons:Special:FilePath/DottedLine.png wiki-commons:Special:FilePath/Interactive_proof_(complexity).svg wiki-commons:Special:FilePath/Randomized_Complexity_Classes.svg wiki-commons:Special:FilePath/SolidLine.png wiki-commons:Special:FilePath/dottedLine.png wiki-commons:Special:FilePath/solidLine.png wiki-commons:Special:FilePath/Turing_machine_2b.svg wiki-commons:Special:FilePath/Complexity_subsets_pspace.svg wiki-commons:Special:FilePath/Decision_Problem.svg wiki-commons:Special:FilePath/Three_input_boolean_circuit.svg
foaf:isPrimaryTopicOf	wikipedia-en:Complexity_class
is dbo:wikiPageDisambiguates of	dbr:Class
is dbo:wikiPageRedirects of	dbr:Time-complexity_class dbr:Canonical_complexity_class dbr:Class_(complexity_theory) dbr:Complexity_classes dbr:Computational_complexity_classes
is dbo:wikiPageWikiLink of	dbr:Sperner's_lemma dbr:PCP_theorem dbr:Oracle_machine dbr:Polynomial-time_reduction dbr:Fragment_(logic) dbr:Spectrum_of_a_sentence dbr:Vertex_cycle_cover dbr:NP-equivalent dbr:NL_(complexity) dbr:Proof_of_impossibility dbr:NP-completeness dbr:P_versus_NP_problem dbr:Computably_enumerable_set dbr:True_quantified_Boolean_formula dbr:Complexity dbr:NEXPTIME dbr:NP-intermediate dbr:Dyck_language dbr:Immerman–Szelepcsényi_theorem dbr:Hamiltonian_path_problem dbr:Solovay–Strassen_primality_test dbr:FNP_(complexity) dbr:TFNP dbr:Computer_bridge dbr:List_of_algorithm_general_topics dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Discrete_mathematics dbr:NP_(complexity) dbr:Complement_(complexity) dbr:Parity_P dbr:Cook–Levin_theorem dbr:Description_logic dbr:LOGCFL dbr:St-connectivity dbr:Polynomial_hierarchy dbr:Quantum_information dbr:Quantum_supremacy dbr:Class dbr:EXPTIME dbr:E_(complexity) dbr:ESPACE dbr:Hamiltonian_completion dbr:Double_exponential dbr:NE_(complexity) dbr:NL-complete dbr:Stathis_Zachos dbr:2-EXPTIME dbr:Parent–teacher_conference dbr:SL_(complexity) dbr:Game_complexity dbr:Golomb_ruler dbr:DSPACE dbr:DTIME dbr:Logic dbr:Formal_language dbr:Monte_Carlo_algorithm dbr:Transitive_closure dbr:NSPACE dbr:Descriptive_complexity_theory dbr:Existential_theory_of_the_reals dbr:FL_(complexity) dbr:Algorithmic_game_theory dbr:Binary_decision_diagram dbr:Calculation dbr:Gap_theorem dbr:Co-NP dbr:Handshaking_lemma dbr:FP_(complexity) dbr:Circuit_complexity dbr:Probabilistically_checkable_proof dbr:♯P-complete dbr:L_(complexity) dbr:Probabilistic_Turing_machine dbr:RP_(complexity) dbr:Go_and_mathematics dbr:Implicit_graph dbr:RL_(complexity) dbr:Number_sign dbr:NP-easy dbr:Las_Vegas_algorithm dbr:Theoretical_computer_science dbr:Complete_(complexity) dbr:Cobham's_thesis dbr:Jack_Edmonds dbr:Juris_Hartmanis dbr:Neil_Immerman dbr:Walter_Savitch dbr:Quantum_algorithm dbr:Blum_axioms dbr:Boolean_satisfiability_problem dbr:ZPP_(complexity) dbr:Complexity_class dbr:List_of_complexity_classes dbr:RE_(complexity) dbr:Reduction_(complexity) dbr:UP_(complexity) dbr:Glossary_of_areas_of_mathematics dbr:NTIME dbr:TC_(complexity) dbr:DLOGTIME dbr:PolyL dbr:Pseudorandom_permutation dbr:QIP_(complexity) dbr:Sparse_language dbr:Unary_language dbr:Alternating_Turing_machine dbr:BQP dbr:Regular_language dbr:P_(complexity) dbr:Interactive_proof_system dbr:Component_(graph_theory) dbr:Graph_isomorphism_problem dbr:CC_(complexity) dbr:List_of_mathematical_logic_topics dbr:Structural_complexity_theory dbr:TC0 dbr:P/poly dbr:PLS_(complexity) dbr:PPAD_(complexity) dbr:PPA_(complexity) dbr:PPP_(complexity) dbr:AC_(complexity) dbr:Computational_resource dbr:Time_complexity dbr:Computational_problem dbr:Advice_(complexity) dbr:Finite_model_theory dbr:L/poly dbr:LH_(complexity) dbr:Ordinal_analysis dbr:Time_hierarchy_theorem dbr:Glossary_of_artificial_intelligence dbr:AC0 dbr:Travelling_salesman_problem dbr:Randomized_algorithm dbr:Shor's_algorithm dbr:Second-order_logic dbr:Algorithm_characterizations dbr:Circuit_(computer_science) dbr:♯P-completeness_of_01-permanent dbr:PostBQP dbr:Exponential_hierarchy dbr:2-satisfiability dbr:APX dbr:Nati_Linial dbr:Natural_proof dbr:Dynamic_epistemic_logic dbr:Bernstein–Vazirani_algorithm dbr:Decision_problem dbr:Integer_factorization dbr:Compression_theorem dbr:Computational_complexity dbr:Computational_hardness_assumption dbr:Integral_polytope dbr:Low_(complexity) dbr:Nyotron dbr:Resource_bounded_measure dbr:Elliptic_curve_only_hash dbr:Arthur–Merlin_protocol dbr:BIT_predicate dbr:BPL_(complexity) dbr:Leaf_language dbr:Quantum_complexity_theory dbr:Wiener_connector dbr:Hidden_linear_function_problem dbr:S2P_(complexity) dbr:SC_(complexity) dbr:NP/poly dbr:Polynomial_creativity dbr:Rotation_distance dbr:Alan_Selman dbr:Enumeration_algorithm dbr:ELEMENTARY dbr:Glossary_of_quantum_computing dbr:SNP_(complexity) dbr:Bounded_arithmetic dbr:Descriptive_Complexity dbr:PH_(complexity) dbr:AWPP_(complexity) dbr:Time-complexity_class dbr:Canonical_complexity_class dbr:Class_(complexity_theory) dbr:Complexity_classes dbr:Computational_complexity_classes
is rdfs:seeAlso of	dbr:P_versus_NP_problem
is foaf:primaryTopic of	wikipedia-en:Complexity_class