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://web.archive.org/web/20190827233504/https:/complexityzoo.uwaterloo.ca/Complexity_Zoo 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://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 http://www.cs.umass.edu/~immerman/complexity_theory.html https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf https://eccc.weizmann.ac.il/report/2017/004/ https://complexityzoo.uwaterloo.ca/Complexity_Zoo https://courses.cs.washington.edu/courses/cse431/14sp/scribes/lec16.pdf https://archive.org/details/computationalcom00aror 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
dbo:wikiPageWikiLink	dbr:Bit dbr:Co-NP dbr:Computability dbr:Logarithmic_growth dbr:List_of_undecidable_problems dbr:Polynomial-time_reduction dbr:FP_(complexity) dbr:Recursive_language dbr:Closure_(mathematics) dbr:BPL_(complexity) dbr:File:Three_input_Boolean_circuit.jpg dbr:Computer dbr:Quantum_Turing_machine dbr:Statistical_physics dbr:University_of_Waterloo dbr:Algorithm dbr:Binary_number dbr:Byte dbr:Cryptography dbr:Economics dbr:Function_(mathematics) dbr:Linguistics dbr:Turing_machine dbr:University_of_Washington dbr:ZPP_(complexity) dbr:Abstract_machine dbr:Processor_(computing) dbr:Alphabet_(formal_languages) dbr:Primality_test dbr:Multitape_Turing_machine dbr:PSPACE dbr:Computational_complexity_theory dbr:Formal_language dbr:Formal_verification dbr:Mathematical_proof dbr:Princeton_University dbr:Logical_connective dbr:Natural_number dbr:Prime_number dbr:Exponential_function dbr:Promise_problem dbr:Prentice_Hall dbr:Decision_problem dbr:IP_(complexity) dbr:Quantum_information_science dbr:BPP_(complexity) dbr:Complexity_class dbr:Recursively_enumerable_language dbr:Yes-no_question dbr:Polynomial dbr:Set_(mathematics) dbr:AND_gate dbr:OR_gate dbr:Big_O_notation dbr:String_(computer_science) dbr:Subset dbr:Boolean_function dbr:Michael_Garey dbr:Parallel_algorithm dbr:Optimization_problem dbr:FNP_(complexity) dbr:Certificate_(complexity) dbr:Planar_graph dbr:Approximation_algorithm dbr:Blum_axioms dbr:Church–Turing_thesis dbr:Computational_complexity dbr:Counting_problem_(complexity) dbr:David_S._Johnson dbr:Interactive_proof_system dbr:Logic_gate dbr:Model_of_computation dbr:NL_(complexity) dbr:NP_(complexity) dbr:Neil_Immerman dbr:Savitch's_theorem dbr:Boolean_circuit dbr:Polynomial_hierarchy dbr:NEXPTIME dbr:Quantum_computer dbr:Directed_acyclic_graph dbr:List_of_complexity_classes dbr:Nondeterministic_Turing_machine dbr:RP_(complexity) dbr:Computational_model dbr:Space_complexity dbr:BQP dbr:Logical_conjunction dbr:Negation dbr:Regular_grammar dbr:Nondeterministic_algorithm dbr:Randomized_algorithm dbr:Context-free_grammar dbr:QIP_(complexity) dbr:QMA dbr:RL_(complexity) dbr:Computational_problem dbr:Computability_theory dbr:P_(complexity) dbr:Time_complexity dbr:Log-space_reduction dbr:Open_problem dbr:Probabilistic_Turing_machine dbr:EXPTIME dbr:AC_(complexity) dbr:Context-sensitive_grammar dbr:Function_problem dbr:Complete_(complexity) dbr:PP_(complexity) dbr:EXPSPACE dbr:NC_(complexity) dbr:Polynomial_time dbr:Time_hierarchy_theorem dbr:Undecidable_problem dbc:Complexity_classes dbc:Computational_complexity_theory dbc:Measures_of_complexity dbc:Theoretical_computer_science dbr:P/poly dbr:Space_hierarchy_theorem dbr:Sharp-P dbr:Karp_reduction dbr:Advice_(complexity) dbr:Interactive_proof_systems dbr:NP-complete dbr:University_of_Maryland dbr:NOT_gate dbr:Recursively_enumerable_set dbr:NP-hard dbr:Recursive_set dbr:Deterministic dbr:Digital_circuit dbr:MA_(complexity) dbr:Network_design dbr:Probabilistic_algorithm dbr:Deterministic_Turing_machine dbr:Disjunction dbr:Upper_bound dbr:AM_(complexity) dbr:Co-RP dbr:P_versus_NP dbr:Randomized_Logarithmic-space_Polynomial-time dbr:Randomized_computation dbr:Bounded-error_probabilistic_polynomial dbr:Directed_path dbr:Cook_reduction dbr:One-sided_error dbr:Two-sided_error dbr:Levin_reduction dbr:Primality_testing dbr:Logarithmic_function dbr:Statistical_estimation dbr:Simple_cycle 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
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_encyclopedia dbt:Cite_web dbt:Efn dbt:Expand_section dbt:Main dbt:Main_article dbt:Mvar dbt:Notelist dbt:Reflist dbt:See_also dbt:Sfn dbt:Sfnp dbt:Short_description dbt:Snf dbt:Webarchive dbt:ComplexityClasses
dct:subject	dbc:Complexity_classes dbc:Computational_complexity_theory dbc:Measures_of_complexity dbc:Theoretical_computer_science
gold:hypernym	dbr:Set
rdf:type	owl:Thing owl:Thing
rdfs:label	Komplexitätsklasse (de) Classe de complexitat (ca) Complexity class (en) قسم تعقيد (ar) Clase de complejidad (es) Classe de complexité (fr) Classe di complessità (it) 복잡도 종류 (ko) 複雑性クラス (ja) 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	freebase:Complexity class yago-res:Complexity class wikidata:Complexity class dbpedia-de:Complexity class dbpedia-es:Complexity class dbpedia-it:Complexity class dbpedia-nl:Complexity class dbpedia-pl:Complexity class dbpedia-fr:Complexity class dbpedia-he:Complexity class dbpedia-ja:Complexity class dbpedia-pt:Complexity class dbpedia-ro:Complexity class dbpedia-ru:Complexity class dbpedia-zh:Complexity class dbpedia-sv:Complexity class dbpedia-ko:Complexity class dbpedia-ca:Complexity class dbpedia-ar:Complexity class dbpedia-fa: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
prov:wasDerivedFrom	wikipedia-en:Complexity_class?oldid=1312245400&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Complexity_subsets_pspace.svg wiki-commons:Special:FilePath/Decision_Problem.svg 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/Three_input_boolean_circuit.svg
foaf:isPrimaryTopicOf	wikipedia-en:Complexity_class
is dbo:wikiPageDisambiguates of	dbr:Class
is dbo:wikiPageRedirects of	dbr:Canonical_complexity_class dbr:Class_(complexity_theory) dbr:Complexity_classes dbr:Computational_complexity_classes dbr:Time-complexity_class
is dbo:wikiPageWikiLink of	dbr:Canonical_complexity_class dbr:APX dbr:Double_exponential dbr:Elliptic_curve_only_hash dbr:Co-NP dbr:Handshaking_lemma dbr:Integral_polytope dbr:Gap_theorem dbr:NP-equivalent dbr:Polynomial-time_reduction dbr:FP_(complexity) dbr:BPL_(complexity) dbr:DSPACE dbr:DTIME dbr:Logic dbr:Theoretical_computer_science dbr:ZPP_(complexity) dbr:Computational_resource dbr:NSPACE dbr:Discrete_mathematics dbr:Formal_language dbr:Golomb_ruler dbr:Computably_enumerable_set dbr:Binary_decision_diagram dbr:Boolean_satisfiability_problem dbr:Decision_problem dbr:CC_(complexity) dbr:Quantum_complexity_theory dbr:Monte_Carlo_algorithm dbr:TC0 dbr:Complexity_class dbr:Calculation dbr:Number_sign dbr:P_versus_NP_problem dbr:Shor's_algorithm dbr:Integer_factorization dbr:Solovay–Strassen_primality_test dbr:PostBQP dbr:Hamiltonian_completion dbr:Rotation_distance dbr:True_quantified_Boolean_formula dbr:Descriptive_Complexity dbr:Alan_Selman dbr:Stathis_Zachos dbr:NTIME dbr:FNP_(complexity) dbr:Algorithmic_game_theory dbr:Bernstein–Vazirani_algorithm dbr:Blum_axioms dbr:Cobham's_thesis dbr:Computational_complexity dbr:Finite_model_theory dbr:Interactive_proof_system dbr:Jack_Edmonds dbr:Juris_Hartmanis dbr:NL_(complexity) dbr:NP_(complexity) dbr:Neil_Immerman dbr:Quantum_information dbr:Polynomial_hierarchy dbr:Dyck_language dbr:St-connectivity dbr:TFNP dbr:Component_(graph_theory) dbr:Description_logic dbr:Bounded_arithmetic dbr:Descriptive_complexity_theory dbr:NEXPTIME dbr:DLOGTIME dbr:Regular_language dbr:Circuit_complexity dbr:L_(complexity) dbr:List_of_complexity_classes dbr:RP_(complexity) dbr:Arthur–Merlin_protocol dbr:PLS_(complexity) dbr:Probabilistically_checkable_proof dbr:♯P-complete dbr:Existential_theory_of_the_reals dbr:FL_(complexity) dbr:L/poly dbr:LH_(complexity) dbr:Cook–Levin_theorem dbr:NP-completeness dbr:Ordinal_analysis dbr:Second-order_logic dbr:Sperner's_lemma dbr:Walter_Savitch dbr:BQP dbr:NP-easy dbr:Vertex_cycle_cover dbr:PH_(complexity) dbr:Dynamic_epistemic_logic dbr:TC_(complexity) dbr:ESPACE dbr:Complement_(complexity) dbr:Natural_proof dbr:Parity_P dbr:Randomized_algorithm dbr:AC0 dbr:Circuit_(computer_science) dbr:QIP_(complexity) dbr:Quantum_algorithm dbr:Alternating_Turing_machine dbr:Nati_Linial dbr:Complexity dbr:RL_(complexity) dbr:NP-intermediate dbr:Computational_problem dbr:Compression_theorem dbr:Computational_hardness_assumption dbr:Travelling_salesman_problem dbr:P_(complexity) dbr:Hamiltonian_path_problem dbr:Time_complexity dbr:LOGCFL dbr:♯P-completeness_of_01-permanent dbr:Parent–teacher_conference dbr:Immerman–Szelepcsényi_theorem dbr:Probabilistic_Turing_machine dbr:Nyotron dbr:Las_Vegas_algorithm dbr:EXPTIME dbr:E_(complexity) dbr:Exponential_hierarchy dbr:AC_(complexity) dbr:Reduction_(complexity) dbr:Transitive_closure dbr:BIT_predicate dbr:Graph_isomorphism_problem dbr:2-satisfiability dbr:Implicit_graph dbr:Structural_complexity_theory dbr:Game_complexity dbr:RE_(complexity) dbr:UP_(complexity) dbr:Complete_(complexity) dbr:Class dbr:Oracle_machine dbr:PCP_theorem dbr:Algorithm_characterizations dbr:Time_hierarchy_theorem dbr:List_of_mathematical_logic_topics dbr:Proof_of_impossibility dbr:Computer_bridge dbr:List_of_algorithm_general_topics dbr:PolyL dbr:Glossary_of_areas_of_mathematics dbr:Go_and_mathematics dbr:Low_(complexity) dbr:SL_(complexity) dbr:S2P_(complexity) dbr:SC_(complexity) dbr:Unary_language dbr:Quantum_supremacy dbr:NE_(complexity) dbr:NL-complete dbr:Pseudorandom_permutation dbr:P/poly dbr:PPAD_(complexity) dbr:PPA_(complexity) dbr:PPP_(complexity) dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:SNP_(complexity) dbr:Enumeration_algorithm dbr:Sparse_language dbr:Wiener_connector dbr:Leaf_language dbr:Resource_bounded_measure dbr:Fragment_(logic) dbr:Spectrum_of_a_sentence dbr:Hidden_linear_function_problem dbr:Advice_(complexity) dbr:NP/poly dbr:Polynomial_creativity dbr:ELEMENTARY dbr:2-EXPTIME dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_quantum_computing dbr:AWPP_(complexity) dbr:Class_(complexity_theory) dbr:Complexity_classes dbr:Computational_complexity_classes dbr:Time-complexity_class
is rdfs:seeAlso of	dbr:P_versus_NP_problem
is foaf:primaryTopic of	wikipedia-en:Complexity_class