This HTML5 document contains 1180 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n29https://www.worldscientific.com/worldscibooks/10.1142/11270%7Cdoi=10.1142/
n22https://www.springer.com/sgw/cda/frontpage/
dbpedia-nlhttp://nl.dbpedia.org/resource/
dbpedia-nohttp://no.dbpedia.org/resource/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-hrhttp://hr.dbpedia.org/resource/
n67https://mathoverflow.net/q/
dctermshttp://purl.org/dc/terms/
dbpedia-dehttp://de.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
n7http://ast.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
n37https://complexityzoo.net/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-thhttp://th.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbpedia-elhttp://el.dbpedia.org/resource/
dbpedia-mshttp://ms.dbpedia.org/resource/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-shhttp://sh.dbpedia.org/resource/
dbpedia-skhttp://sk.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-jahttp://ja.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
n60http://tl.dbpedia.org/resource/
n38http://dbpedia.org/resource/P/
n27http://commons.wikimedia.org/wiki/Special:FilePath/
n42https://global.dbpedia.org/id/
n23http://www.wisdom.weizmann.ac.il/~oded/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
n48http://dbpedia.org/resource/Max/min_CSP/
n14http://dbpedia.org/resource/NP/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
yago-reshttp://yago-knowledge.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-bghttp://bg.dbpedia.org/resource/
dbpedia-rohttp://ro.dbpedia.org/resource/
goldhttp://purl.org/linguistics/gold/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
dbpedia-euhttp://eu.dbpedia.org/resource/
n66http://bn.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
freebasehttp://rdf.freebase.com/ns/
n6http://dbpedia.org/resource/File:
dbthttp://dbpedia.org/resource/Template:
n54http://people.cs.uchicago.edu/~fortnow/papers/
n65http://dbpedia.org/resource/Glossary_of_engineering:
n51http://d-nb.info/gnd/
n13http://portal.acm.org/
dbpedia-cshttp://cs.dbpedia.org/resource/
dbpedia-arhttp://ar.dbpedia.org/resource/
n25http://dbpedia.org/resource/L/
dbphttp://dbpedia.org/property/
dbpedia-ruhttp://ru.dbpedia.org/resource/
n10https://www.scottaaronson.com/papers/
yagohttp://dbpedia.org/class/yago/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n40http://www.cs.princeton.edu/theory/complexity/
dbpedia-simplehttp://simple.dbpedia.org/resource/
n35http://dbpedia.org/resource/Wikt:
dbpedia-ithttp://it.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:Carsten_Lund
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Amin_Shokrollahi
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Belief_revision
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Primitive_recursive_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Proof_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Proof_of_impossibility
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Proximity_problems
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pseudo-polynomial_transformation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Quantum_complexity_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Quantum_logic_gate
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Rod_Downey
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Rolf_Niedermeier
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ronald_V._Book
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:knownFor
dbr:Computational_complexity_theory
Subject Item
dbr:Rosetta@home
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Santa_Fe_Institute
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Scott_Aaronson
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:fields
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Electronic_Colloquium_on_Computational_Complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Element_distinctness_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Elias_Koutsoupias
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Enumeration_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Enumeration_reducibility
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_University_of_California,_Berkeley_alumni
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_University_of_California,_Berkeley_faculty
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_academic_fields
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_algorithm_general_topics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_atheists_in_science_and_technology
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_complexity_classes
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_computer_science_conferences
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_computer_scientists
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_eponymous_laws
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Mem_(computing)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Memoization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Michael_Saks_(mathematician)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Moore_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Myhill_isomorphism_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NE_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:No_free_lunch_in_search_and_optimization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:MAX-3LIN-EQN
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:MAX-3SAT
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:MD5
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:MIT_Electrical_Engineering_and_Computer_Science_Department
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Tridiagonal_matrix
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:One_Clean_Qubit
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Parity_P
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Parsimonious_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Partial_correlation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Partially_observable_Markov_decision_process
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Strong_NP-completeness
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Probably_approximately_correct_learning
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Primality_Testing_for_Beginners
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Primality_test
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Bella_Subbotovskaya
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Bernoulli_number
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Binary_search_tree
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Blum_Blum_Shub
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Book_embedding
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Branches_of_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:David_Shmoys
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:field
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Algorithmic_Geometry
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Algorithmic_efficiency
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Algorithmic_information_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Anne_Condon
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Append
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Approximation-preserving_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Arbitrary-precision_arithmetic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:History_of_computational_complexity_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:John_von_Neumann
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Joseph_F._Traub
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_University_of_Edinburgh_people
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_fellows_of_the_Fields_Institute
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_important_publications_in_computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_important_publications_in_theoretical_computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_pioneers_in_computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pathological_(mathematics)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Patrick_C._Fischer
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Paul_Schupp
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Paul_Vitányi
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Peter_Bürgisser
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:knownFor
dbr:Computational_complexity_theory
Subject Item
dbr:Richard_E._Ladner
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Richard_E._Stearns
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Richard_M._Karp
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:DLOGTIME
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:DPLL_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:DSPACE
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:DTIME
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ulrike_Sattler
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Universality_probability
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:University_of_Warwick
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:CCT
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageDisambiguates
dbr:Computational_complexity_theory
Subject Item
dbr:Vertex_cover
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Viliam_Geffert
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:field
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Vincent's_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Virginia_Vassilevska_Williams
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Visual_search_engine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Deborah_Joseph
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Decision_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Decision_tree_model
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Descriptive_Complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Descriptive_complexity_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Design_for_testing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dominic_Welsh
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Double-ended_queue
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Double_exponential_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dynamic_lot-size_model
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dynamic_problem_(algorithms)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:ESPACE
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:EXPSPACE
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Independent_set_(graph_theory)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Index_of_computing_articles
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Index_of_philosophy_articles_(A–C)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Index_of_software_engineering_articles
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Index_set
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Induced_subgraph_isomorphism_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Induction_puzzles
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Institute_for_System_Programming
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Integer_circuit
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Interactive_proof_system
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:International_Association_for_Cryptologic_Research
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Interpolation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Jaikumar_Radhakrishnan
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Kurds_in_Israel
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:L-notation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:L-reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
n25:poly
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Limits_of_computation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_important_publications_in_mathematics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_lemmas
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_mathematical_logic_topics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_mathematical_theories
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_multiple_discoveries
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_people_from_Negros_Occidental
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Intractability_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Pierluigi_Crescenzi
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Topological_index
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PSPACE-complete
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Presburger_arithmetic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Worst-case_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pseudo-polynomial_time
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pseudomathematics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pseudorandom_generator
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pseudorandomness
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Reasoning_system
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Security_parameter
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Topological_combinatorics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Simon's_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Space_hierarchy_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Timeline_of_Polish_science_and_technology
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Timeline_of_women_in_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:♯P
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:♯P-complete
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:♯P-completeness_of_01-permanent
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:(SAT,_ε-UNSAT)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_measure
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computability
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computability_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computable_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_infeasibility
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Computing_the_permanent
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Cryptographic_hash_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Cryptography
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Analysis_of_algorithms
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ancestral_reconstruction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Mathematical_logic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Mathematical_optimization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Mathematics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Median
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ryan_Williams_(computer_scientist)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:fields
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:SL_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ellipsoid_method
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Error_correction_code
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Generalized_game
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Generalized_geography
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Generic-case_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Geometric_complexity_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Geometric_group_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Low_and_high_hierarchies
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Novikov_self-consistency_principle
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:One-way_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Oracle_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Private_biometrics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Token_reconfiguration
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Russell_Impagliazzo
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:knownFor
dbr:Computational_complexity_theory
Subject Item
dbr:Valiant–Vazirani_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Silver–Meal_heuristic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NP-easy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Rectilinear_Steiner_tree
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Special_number_field_sieve
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Yuri_Petrovich_Ofman
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Structural_rule
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Schaefer's_dichotomy_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Salil_Vadhan
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:field
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Seinosuke_Toda
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:QMA
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Quantum_information_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Quasiconvex_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:RSA_Award_for_Excellence_in_Mathematics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Christoph_Meinel
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Christos_Papadimitriou
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Chromatic_polynomial
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Church–Turing_thesis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Clique_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Co-NP
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Edward_Nelson
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Eliezer_Yudkowsky
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Enumeration
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Frankl–Rödl_graph
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Fu_Foundation_School_of_Engineering_and_Applied_Science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Gabriel_Lamé
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Game_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Gap_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:General_number_field_sieve
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:General_recursive_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Georg_Gottlob
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:George_Cowan
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Glossary_of_areas_of_mathematics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Glossary_of_artificial_intelligence
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Glossary_of_computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
n65:_M–Z
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Glossary_of_quantum_computing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Bounded_arithmetic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Model_checking
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NC_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NL_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Concatenated_error_correction_code
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Configuration_graph
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Conjunctive_normal_form
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Connected-component_labeling
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Constraint_satisfaction_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Constructible_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Continuous-variable_quantum_information
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Contraction_hierarchies
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Cook–Levin_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Creative_and_productive_sets
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Crossing_Numbers_of_Graphs
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Crossing_sequence_(Turing_machines)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dana_Angluin
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Erez_Petrank
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:LH_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:LOGCFL
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:L_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Laboratory_for_Foundations_of_Computer_Science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Zig-zag_product
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Programming_complexity
owl:differentFrom
dbr:Computational_complexity_theory
Subject Item
dbr:Statistical_inference
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:1985_in_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Andrzej_Grzegorczyk
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Anonymous_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Applesoft_BASIC
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Arithmetic_circuit_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Benjamin_Rossman
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Lenore_Blum
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Leonid_Levin
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Leslie_Valiant
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Li_Cai_(psychometrician)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Linear_optical_quantum_computing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Logarithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Logic_of_graphs
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Louise_Hay_(mathematician)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:László_Babai
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:MAXEkSAT
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:MPEG-1
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Blum's_speedup_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Blum_axioms
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Shmuel_Winograd
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Shogi
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Small_caps
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Stephen_Cook
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Steven_Rudich
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:subDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Claw_finding_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Clique_cover
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Collision_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Combinatorial_optimization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Combinatorial_search
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Combinatorics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Communication_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Community_structure
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Complement_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Complete_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_and_Real_Computation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_class
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_of_constraint_satisfaction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Component_(graph_theory)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Compression_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computably_enumerable_set
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_Complexity_Conference
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_Optimization_and_Applications
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_complexity_theory
rdf:type
yago:Algorithm105847438 yago:DataStructure105728493 yago:YagoPermanentlyLocatedEntity yago:Arrangement105726596 yago:Cognition100023271 yago:WikicatAlgorithms yago:Activity100407535 yago:Structure105726345 yago:Procedure101023820 yago:Rule105846932 yago:PsychologicalFeature100023100 yago:Event100029378 owl:Thing yago:Abstraction100002137 yago:WikicatDataStructures dbo:Organisation yago:Act100030358
rdfs:label
Teoría de la complejidad computacional Konplexutasun konputazionalaren teoria Théorie de la complexité (informatique théorique) 계산 복잡도 이론 Теория сложности вычислений Teorie složitosti Теорія складності обчислень نظرية التعقيد الحسابي Θεωρία πολυπλοκότητας 計算複雑性理論 Computational complexity theory Komplexitätstheorie Teoria della complessità computazionale Teoria de la complexitat computacional Computationele complexiteitstheorie 計算複雜性理論
rdfs:comment
Konplexutasun konputazionalaren teoria edo konplexutasun informatikoaren teoria teoria konputazionalaren adar bat da, arazo konputazionalak berezko zailtasunaren arabera sailkatzean eta konplexutasun klase horien arteko erlazioan oinarritzen dena. Konplexutasun konputazionalaren teoria baliabide kopuru jakin batekin ebatzi daitezkeen edo ezin diren arazoak sailkatzen saiatzen da. Era berean, baliabide horiei, murrizketak ezartzea da konputagarritasunaren teoriatik bereizten duena, hau da, zer-nolako arazok ebatzi daitezkeen algoritmikoki. La teoria de la complexitat computacional se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si. Un problema computacional és una tasca resolta per un ordinador. Un problema de càlcul es pot resoldre mitjançant l'aplicació mecànica de passos matemàtics, com ara un algorisme. Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному це тривалість обчислень або необхідний обсяг пам'яті. В окремих випадках досліджуються інші міри складності, такі як розмір мікросхем, або кількість процесорів, необхідна для роботи паралельних алгоритмів. Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven. Een computationeel probleem is een probleem dat door een computer kan worden opgelost. Een voorbeeld van een probleem dat computationeel is, is de vraag of een getal wel of niet priem is. Dit kan worden bepaald door middel van een priemgetaltest. Een probleem wordt gezien als inherent moeilijk, als het voor alle denkbare algoritmes veel tijd of geheugen in beslag neemt. Computationele complexiteitstheorie beschrijft dus de praktische limieten van computers. 계산 복잡도 이론(計算 複雜度 理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다. Η θεωρία πολυπλοκότητας είναι το μέρος εκείνο της θεωρίας υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της και κεντρικό γνωστικό πεδίο της επιστήμης υπολογιστών. Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen. Die Komplexität eines Problems ist wiederum die Komplexität desjenigen Algorithmus, der das Problem mit dem geringstmöglichen Ressourcenverbrauch löst. In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. La teoría de la complejidad computacional​ o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad.​ La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema. Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce dunque alle risorse di calcolo richieste. I problemi sono classificati in differenti classi di complessità, in base all'efficienza del migliore algoritmo noto in grado di risolvere quello specifico problema. 计算复杂性理论(Computational complexity theory)是理论计算机科学和数学的一个分支,它致力于将可计算问题根据它们本身的复杂性分类,以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题,亦即这个问题可以用一系列机械的数学步骤解决,例如算法。 如果一个问题的求解需要相当多的资源(无论用什么算法),则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源(时间和空间),从而将资源的确定方法正式化了。其他复杂性测度同样被运用,比如通信量(应用于通信复杂性),电路中门的数量(应用于电路复杂性)以及中央处理器的数量(应用于并行计算)。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域,与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量,而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说,它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地,在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标:后者关心的是何种问题原则上可以用算法解决。 Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов. نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها. وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به. 計算複雑性理論(けいさんふくざつせいりろん、英: computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。 「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。 Teorie složitosti je odvětvím v informatice a matematice, které se zaměřuje na klasifikaci dle jejich vlastní složitosti a určení vztahů mezi nimi. Ke studiu a určení složitosti těchto problémů definuje výpočetní modely, jako je Turingův stroj nebo RAM, na kterých je simuluje a určuje složitost (typicky časovou a paměťovou). Používají se i další míry složitosti, jako množství komunikace (v ), počet hradel obvodu (ve ), počet přístupů do keše (v analýze kešování) a počet procesorů (v paralelním programování). Jeden z cílů teorie složitosti je určit praktické limity toho, co počítače dokážou spočítat a co ne. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée …) requis par un algorithme pour résoudre un problème algorithmique. Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité.
rdfs:seeAlso
dbr:Combinatorial_explosion
foaf:depiction
n27:Turing_machine_2b.svg n27:Sorting_quicksort_anim.gif n27:Complexity_classes.svg n27:Complexity_subsets_pspace.svg n27:TSP_Deutschland_3.png n27:Decision_Problem.svg
dcterms:subject
dbc:Computational_complexity_theory dbc:Computational_fields_of_study
dbo:wikiPageID
7543
dbo:wikiPageRevisionID
1120968876
dbo:wikiPageWikiLink
dbr:Boris_Trakhtenbrot dbr:Parallel_computing dbr:Primality_testing dbr:Blum_complexity_axioms dbr:John_Myhill dbr:Euclidean_algorithm dbr:NTIME dbr:Cobham–Edmonds_thesis n6:Complexity_subsets_pspace.svg dbr:Probability_distribution dbr:Descriptive_complexity_theory dbr:Alphabet_(computer_science) dbr:Decision_problem dbr:Probabilistic_Turing_machine dbr:NP_(complexity) n6:Turing_machine_2b.svg dbr:Computer dbr:Optimization_problem dbr:NP-complete dbr:NP-hard dbr:List_of_unsolved_problems_in_computer_science dbr:Jack_Edmonds dbr:Millennium_Prize_Problems dbr:Alan_Turing dbr:Total_function n6:TSP_Deutschland_3.png dbr:L_(complexity) dbr:Counting_problem_(complexity) dbc:Computational_complexity_theory dbr:RP_(complexity) dbr:Integer dbr:Integer_programming dbr:NP-intermediate dbr:Boolean_circuit dbr:NEXPTIME dbr:Algorithm dbr:Computational_problem dbr:AC_(complexity) dbr:Graph_(discrete_mathematics) dbr:Clay_Mathematics_Institute dbr:Deterministic_Turing_machine dbr:Age_of_the_universe dbr:Presburger_arithmetic dbr:Discrete_logarithm_problem dbr:László_Babai dbr:Switching_theory dbr:Space_hierarchy_theorem dbr:Limits_of_computation dbr:Computational_complexity dbr:Computational_complexity_of_mathematical_operations dbr:Complexity dbr:BPP_(complexity) dbr:Cobham's_thesis dbr:Logic_gate dbr:Biology dbr:Prime_factorization dbr:Binary_notation dbr:Best,_worst_and_average_case dbr:Space_complexity dbr:General_number_field_sieve dbr:Non-deterministic_time dbr:Alternating_Turing_machine dbr:Proof_complexity dbr:Amortized_analysis dbr:Information_based_complexity dbr:Time_hierarchy_theorem dbr:P_(complexity) dbr:Communication_complexity n35:infeasible n35:intractable dbr:Boolean_satisfiability_problem dbr:Church–Turing_thesis dbr:Dynamical_system dbr:Monotone_circuit dbr:Linear_time dbr:Analog_computation dbr:Quantum_algorithm dbr:EXPTIME dbr:Vertex_cover_problem dbr:Randomized_algorithm dbr:Axiom dbr:IP_(complexity) dbr:Richard_E._Stearns dbr:Sharp-P dbr:Feasible_solution n6:Complexity_classes.svg dbr:Theoretical_computer_science dbr:Eugene_Luks dbr:Knapsack_problem dbr:EXPSPACE dbr:AM_(complexity) dbr:PP_(complexity) dbr:Non-deterministic_algorithm dbr:Transcomputational_problem dbr:Deterministic_algorithm dbr:Parameterized_complexity dbr:Complete_(complexity) dbr:NEXPSPACE dbr:Leonid_Levin dbr:NL_(complexity) dbr:Linear_bounded_automata dbr:RSA_(algorithm) dbr:P_versus_NP_problem dbr:Numerical_analysis dbr:Log-space_reduction dbr:List_of_computability_and_complexity_topics dbr:DTIME dbr:Turing_machine_equivalents dbr:Richard_Karp dbr:Co-NP dbr:Protein_structure_prediction dbr:Promise_problem dbr:Adjacency_list dbr:Adjacency_matrix dbr:Milan dbr:NPSPACE dbr:QMA dbr:Symmetric_Turing_machine dbr:Control_theory dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:PSPACE dbr:Conway's_Game_of_Life dbr:Decision_tree_complexity dbr:List_of_complexity_classes dbr:Mathematical_optimization dbr:Juris_Hartmanis dbr:Mathematics dbr:Shor's_algorithm dbr:Context_of_computational_complexity n6:Sorting_quicksort_anim.gif dbr:Lambda_calculus dbr:Hamiltonian_path_problem dbr:Interactive_proof_system dbr:Random-access_machine dbr:Time_complexity dbr:Quantum_complexity_theory dbr:Game_complexity dbr:BQP dbr:String_(computer_science) dbr:Operations_research dbr:Differential_equation dbc:Computational_fields_of_study dbr:Raymond_Smullyan dbr:Polynomial-time_reduction dbr:Structural_complexity_theory dbr:Graph_theory dbr:FP_(complexity) dbr:NSPACE dbr:Non-deterministic_Turing_machine dbr:Cellular_automata dbr:Big_O_notation dbr:Manuel_Blum dbr:Logistics dbr:Gabriel_Lamé dbr:Bitstring dbr:Function_problem dbr:Combinatorics dbr:DSPACE dbr:Polynomial_time_hierarchy n6:Decision_Problem.svg dbr:Integer_factorization_problem dbr:Polynomial_time dbr:Hisao_Yamada dbr:Blum's_speedup_theorem dbr:Traveling_salesman_problem dbr:Models_of_computation dbr:Blum_axioms dbr:RAM_machine dbr:Analysis_of_algorithms dbr:Formal_language dbr:ALL_(complexity) dbr:Stephen_Cook dbr:Circuit_complexity dbr:Quantum_Turing_machine dbr:Leaf_language dbr:Cook–Levin_theorem dbr:Pure_mathematics dbr:Quicksort dbr:SAT_solver dbr:Discrete_uniform_distribution dbr:NC_(complexity) dbr:Savitch's_theorem dbr:Computability_theory dbr:List_of_important_publications_in_theoretical_computer_science dbr:Connectivity_(graph_theory) dbr:ZPP_(complexity) dbr:Complement_(complexity)
dbo:wikiPageExternalLink
n10:philos.pdf n13:citation.cfm%3Fid=800191.805573 n22:0,11855,5-0-22-1519914-0,00.html n23:cc-book.html n29:11270 n37:Complexity_Zoo n40: n54:history.pdf n67:34487
owl:sameAs
dbpedia-tr:Hesaplamalı_karmaşıklık_teorisi n7:Teoría_de_la_complexidá_computacional dbpedia-sr:Теорија_комплексности dbpedia-eu:Konplexutasun_konputazionalaren_teoria dbpedia-ca:Teoria_de_la_complexitat_computacional dbpedia-ms:Teori_kekompleksan_pengiraan dbpedia-it:Teoria_della_complessità_computazionale dbpedia-uk:Теорія_складності_обчислень dbpedia-sh:Računska_teorija_složenosti yago-res:Computational_complexity_theory dbpedia-fa:نظریه_پیچیدگی_محاسباتی dbpedia-el:Θεωρία_πολυπλοκότητας dbpedia-cs:Teorie_složitosti wikidata:Q205084 dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) n42:woAX dbpedia-simple:Computational_complexity_theory dbpedia-he:תורת_הסיבוכיות dbpedia-ko:계산_복잡도_이론 dbpedia-no:Kompleksitetsteori dbpedia-ru:Теория_сложности_вычислений dbpedia-ar:نظرية_التعقيد_الحسابي dbpedia-de:Komplexitätstheorie n51:4120591-1 freebase:m.023z_ dbpedia-th:ทฤษฎีความซับซ้อนในการคำนวณ dbpedia-nl:Computationele_complexiteitstheorie dbpedia-zh:計算複雜性理論 dbpedia-ro:Teoria_complexității dbpedia-ja:計算複雑性理論 dbpedia-hr:Računska_teorija_složenosti n60:Teorya_ng_komputasyonal_na_komplehidad dbpedia-sk:Teória_zložitosti dbpedia-bg:Теория_на_изчислителната_сложност dbpedia-vi:Lý_thuyết_độ_phức_tạp_tính_toán n66:পরিগণনামূলক_জটিলতা_তত্ত্ব dbpedia-es:Teoría_de_la_complejidad_computacional
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Commonscat dbt:Authority_control dbt:Dead_link dbt:Harv dbt:See_also dbt:Use_mdy_dates dbt:Div_col dbt:Div_col_end dbt:ComplexityClasses dbt:Main dbt:Short_description dbt:Springer dbt:Computer_science dbt:Citation dbt:Visible_anchor dbt:Wikt dbt:Quote dbt:Garey-Johnson
dbo:thumbnail
n27:TSP_Deutschland_3.png?width=300
dbp:bot
InternetArchiveBot
dbp:date
January 2022
dbp:fixAttempted
yes
dbp:id
p/c130160
dbp:title
Computational complexity classes
dbo:abstract
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity. Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically. La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema. Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce dunque alle risorse di calcolo richieste. I problemi sono classificati in differenti classi di complessità, in base all'efficienza del migliore algoritmo noto in grado di risolvere quello specifico problema. Una distinzione informale, ma di grande rilievo, è quella posta tra i cosiddetti problemi facili, di cui si conoscono algoritmi di risoluzione efficienti, e difficili, di cui gli unici algoritmi noti non sono efficienti. Ad esempio la maggior parte della crittografia moderna si fonda sull'esistenza di problemi ritenuti difficili; ha enorme rilevanza lo studio di tali problemi, poiché, qualora si dimostrasse l'esistenza di un algoritmo efficiente per un problema ritenuto difficile, i sistemi crittografici basati su di esso non sarebbero più sicuri. Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному це тривалість обчислень або необхідний обсяг пам'яті. В окремих випадках досліджуються інші міри складності, такі як розмір мікросхем, або кількість процесорів, необхідна для роботи паралельних алгоритмів. Слід не плутати теорію складності обчислень з теорією обчислюваності, яка займається пошуком відповіді на запитання про те, які задачі можуть бути взагалі розв'язані за допомогою алгоритмів. Основна задача досліджень в теорії складності обчислень полягає у класифікації всіх розв'язних задач. Зокрема, робляться спроби відокремити множину задач з ефективними алгоритмами розв'язання від множини важко розв'язних задач. Konplexutasun konputazionalaren teoria edo konplexutasun informatikoaren teoria teoria konputazionalaren adar bat da, arazo konputazionalak berezko zailtasunaren arabera sailkatzean eta konplexutasun klase horien arteko erlazioan oinarritzen dena. Arazo bat berez zaila gisa sailkatzen da, bere konponbideak baliabide konputazional kopuru handia eskatzen badu, erabilitako algoritmoa edozein dela ere. Konplexutasun konputazionalaren teoriak baieztapen hori formalizatzen du arazo horiek aztertzeko eta haiek ebazteko behar diren baliabideen kopuruaren kuantifikaziorako eredu konputazional matematikoak sartuz, hala nola denbora eta memoria. Konplexutasun konputazionalaren teoriaren helburuetako bat ordenagailuan egin daitekeenaren eta egin ezin denaren muga praktikoak zehaztea da. Konplexutasun konputazionalaren teoriarekin lotutako beste alor batzuk algoritmoen analisia eta konputagarritasunaren teoria dira. Algoritmoen analisiaren eta konplexutasun konputazionalaren teoriaren arteko alde nabarmena da lehena algoritmo jakin batek arazo bat ebazteko behar duen baliabide kopurua zehazteaz arduratzen da, eta, bigarrena, berriz, arazo bera ebazteko erabil litezkeen algoritmo posible guztiak aztertzen ditu. Konplexutasun konputazionalaren teoria baliabide kopuru jakin batekin ebatzi daitezkeen edo ezin diren arazoak sailkatzen saiatzen da. Era berean, baliabide horiei, murrizketak ezartzea da konputagarritasunaren teoriatik bereizten duena, hau da, zer-nolako arazok ebatzi daitezkeen algoritmikoki. Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven. Een computationeel probleem is een probleem dat door een computer kan worden opgelost. Een voorbeeld van een probleem dat computationeel is, is de vraag of een getal wel of niet priem is. Dit kan worden bepaald door middel van een priemgetaltest. Een probleem wordt gezien als inherent moeilijk, als het voor alle denkbare algoritmes veel tijd of geheugen in beslag neemt. Computationele complexiteitstheorie beschrijft dus de praktische limieten van computers. 계산 복잡도 이론(計算 複雜度 理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다. La teoría de la complejidad computacional​ o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad.​ Un problema se cataloga como "inherentemente difícil" si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de computación matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos, como tiempo y memoria. Una de las metas de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede hacer en una computadora y qué no. Otros campos relacionados con la teoría de la complejidad computacional son el análisis de algoritmos y la teoría de la computabilidad. Una diferencia significativa entre el análisis de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema. La teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica. Η θεωρία πολυπλοκότητας είναι το μέρος εκείνο της θεωρίας υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της και κεντρικό γνωστικό πεδίο της επιστήμης υπολογιστών. Οι συνηθέστεροι πόροι για τους οποίους ενδιαφερόμαστε είναι ο χρόνος, οπότε μιλάμε για τη χρονική πολυπλοκότητα του αλγορίθμου, δηλαδή πόσα «βήματα» χρειάζεται να εκτελέσει ο αλγόριθμος συναρτήσει της του, και ο χώρος, οπότε μιλάμε για τη χωρική πολυπλοκότητα, δηλαδή πόσο χώρο (μνήμη) χρειάζεται ο αλγόριθμος συναρτήσει της εισόδου του. Εκτός από αυτούς τους πόρους, κατά περίπτωση, μπορεί να ενδιαφερόμαστε και για άλλους, όπως για παράδειγμα πόσοι παράλληλοι επεξεργαστές χρειάζονται για να λυθεί ένα πρόβλημα παράλληλα. Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов. Следует не путать теорию сложности вычислений с теорией вычислимости, которая занимается поиском ответа на вопрос о том, какие задачи могут быть вообще решены с помощью алгоритмов. Основная задача исследований в теории сложности вычислений заключается в классификации всех разрешимых задач. В частности, делаются попытки разделить множество задач с эффективными алгоритмами решения от множества трудно разрешимых задач. نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها. ويمكن اعتبارها مسألة صعبة إذا استخدمت كمية مُعينة من الموارد أياً كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة مثل: الوقت أو حجم المكان الإضافي اللازم، وتوجد معايير تعقيد أخرى مثل: الاتصال (مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية (مستخدم في نظرية تعقيد الدارات المنطقية) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي). وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به. المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات ونظرية الحاسوبية، والفرق بين تحليل الخوارزميات ونظرية التعقيد الحسابية هو أن الأول يسأل عن خوارزمية معينة لحل مسألة، بينما الآخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة، وبالتحديد فإن الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية مُحددة من الموارد، أما وضع الحدود للموارد الموجودة هو ما يميز نظرية التعقيد الحسابي عن النظرية الحاسوبية أي أن النظرية الحاسوبية تسأل عن أية مسائل يمكن حلها بواسطة خوارزمية. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée …) requis par un algorithme pour résoudre un problème algorithmique. Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité. 计算复杂性理论(Computational complexity theory)是理论计算机科学和数学的一个分支,它致力于将可计算问题根据它们本身的复杂性分类,以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题,亦即这个问题可以用一系列机械的数学步骤解决,例如算法。 如果一个问题的求解需要相当多的资源(无论用什么算法),则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源(时间和空间),从而将资源的确定方法正式化了。其他复杂性测度同样被运用,比如通信量(应用于通信复杂性),电路中门的数量(应用于电路复杂性)以及中央处理器的数量(应用于并行计算)。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域,与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量,而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说,它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地,在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标:后者关心的是何种问题原则上可以用算法解决。 La teoria de la complexitat computacional se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si. Un problema computacional és una tasca resolta per un ordinador. Un problema de càlcul es pot resoldre mitjançant l'aplicació mecànica de passos matemàtics, com ara un algorisme. Es considera que un problema és inherentment difícil si la seva solució requereix recursos importants, sigui quin sigui l'algorisme utilitzat. La teoria formalitza aquesta intuïció, introduint models matemàtics de càlcul per estudiar aquests problemes i quantificant-ne la complexitat computacional, és a dir, la quantitat de recursos necessaris per resoldre'ls, com el temps i la necessitat d'emmagatzematge. També s'utilitzen altres mesures de complexitat, com ara la quantitat de comunicació (utilitzada en complexitat de comunicació), el nombre de portes en un circuit (utilitzat en complexitat de circuits) i el nombre de processadors (utilitzat en informàtica paral·lela). Una de les funcions de la teoria de la complexitat computacional és determinar els límits pràctics del que els ordinadors poden i no poden fer. El problema P versus NP, un dels set problemes del Premi del Mil·lenni, està dedicat al camp de la complexitat computacional. Camps estretament relacionats en la informàtica teòrica són l'anàlisi d'algorismes i la teoria de la computabilitat. La primera es dedica a analitzar la quantitat de recursos que necessita un algorisme en particular per resoldre un problema, mentre que la segona fa una pregunta més general sobre tots els possibles algorismes que es podrien utilitzar per resoldre el mateix problema. Més concretament, la teoria de la complexitat computacional intenta classificar problemes que es poden o no resoldre amb recursos restringits adequadament. Al seu torn, imposar restriccions als recursos disponibles és el que distingeix la complexitat computacional de la teoria de la computabilitat: aquesta darrera teoria es pregunta quin tipus de problemes es poden, en principi, resoldre algorítmicament. Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen. Die Komplexität eines Problems ist wiederum die Komplexität desjenigen Algorithmus, der das Problem mit dem geringstmöglichen Ressourcenverbrauch löst. Die Komplexitätstheorie unterscheidet sich von der Berechenbarkeitstheorie, die sich mit der Frage beschäftigt, welche Probleme prinzipiell algorithmisch gelöst werden können. Demgegenüber besteht das wichtigste Forschungsziel der Komplexitätstheorie darin, die Menge aller lösbaren Probleme zu klassifizieren. Insbesondere versucht man, die Menge der effizient lösbaren Probleme, deren Ressourcenverbrauch in der Praxis bewältigt werden kann, von der Menge der inhärent schwierigen Probleme abzugrenzen. 計算複雑性理論(けいさんふくざつせいりろん、英: computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。 「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。 Teorie složitosti je odvětvím v informatice a matematice, které se zaměřuje na klasifikaci dle jejich vlastní složitosti a určení vztahů mezi nimi. Ke studiu a určení složitosti těchto problémů definuje výpočetní modely, jako je Turingův stroj nebo RAM, na kterých je simuluje a určuje složitost (typicky časovou a paměťovou). Používají se i další míry složitosti, jako množství komunikace (v ), počet hradel obvodu (ve ), počet přístupů do keše (v analýze kešování) a počet procesorů (v paralelním programování). Jeden z cílů teorie složitosti je určit praktické limity toho, co počítače dokážou spočítat a co ne. V tomto kontextu je výpočetní problém chápán jako úkol, který lze vyřešit na počítači, čímž se myslí mechanickou aplikací postupných kroků pomocí algoritmu. Konkrétní zadání problému je tzv. instance a algoritmus vrátí řešení instance. Příkladem je situace, kdy chceme zjistit, zdali je nějaké přirozené číslo n prvočíslem nebo ne. Jedná se o rozhodovací problém, kde instancí problému jsou přirozená čísla a výsledkem je odpověď ANO/NE. Problém, například výše zmíněné testování prvočíselnosti, se považuje za těžký, pokud jeho řešení potřebuje značné zdroje bez ohledu na to, jaký algoritmus je použit. Příbuzné oblasti informatiky jsou analýza algoritmů a teorie vyčíslitelnosti. Hlavním rozdílem mezi analýzou algoritmů a teorií složitosti je, že analýza algoritmů se zabývá množstvím potřebných zdrojů, které potřebuje konkrétní algoritmus, zatímco teorie složitosti zjišťuje obecnější otázky týkající se všech algoritmů, které se dají použít pro řešení určitého problému. Snaží se tedy klasifikovat problémy podle daných omezení na dostupné zdroje. Tedy zavedení omezení na dostupné zdroje odlišuje teorii složitosti od teorie vyčíslitelnosti, které se ptá, jaké problémy lze, v principu, vyřešit algoritmicky.
gold:hypernym
dbr:Branch
prov:wasDerivedFrom
wikipedia-en:Computational_complexity_theory?oldid=1120968876&ns=0
dbo:wikiPageLength
49963
foaf:isPrimaryTopicOf
wikipedia-en:Computational_complexity_theory
Subject Item
dbr:Computational_hardness_assumption
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_physics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_resource
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_social_choice
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_topology
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computer_bridge
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computer_performance
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:caption
dbr:Computational_complexity_theory
Subject Item
dbr:Computer_scientist
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Computing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Zvi_Galil
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Function_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Half-exponential_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hardness_of_approximation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hardy_hierarchy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Harry_Buhrman
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Harry_Mairson
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Horn_clause
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Kernel_adaptive_filter
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Kernelization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ketan_Mulmuley
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Key_feedback_mode
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Kousha_Etessami
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Mathematics_of_paper_folding
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PCP_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PH_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PLS_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PPA_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PPP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PTAS_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:P_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Padding_argument
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Perfect_power
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pollard's_kangaroo_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Polynomial_identity_testing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Probabilistically_checkable_proof
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Mahaney's_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Quantum_supremacy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Spanning_tree
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sparse_language
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Standard_model_(cryptography)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Symmetric_space_(disambiguation)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:TC_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Theoretical_computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Theory_of_computation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Many-one_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Markov_brothers'_inequality
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Math_in_Moscow
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Matroid_oracle
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
n48:Ones_classification_theorems
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Maximum_coverage_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Maximum_satisfiability_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
n38:poly
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Shannon_capacity_of_a_graph
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:1971_in_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Avi_Wigderson
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:BPP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:BQP
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Busy_beaver
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Bézout's_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Admissible_rule
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Time_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Transitive_closure
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Travelling_Salesman_(2012_film)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Travelling_salesman_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Tree_transducer
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Turing_Award
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:UP_Diliman_Department_of_Computer_Science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Data_mining
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Database_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Wafer_(electronics)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:William_Gasarch
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Distributed_algorithmic_mechanism_design
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Distributed_computing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Distributed_constraint_optimization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Divide-and-conquer_eigenvalue_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Gadget_(computer_science)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Game_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Games,_Puzzles,_and_Computation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Gap_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Giovanni_Pighizzini
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Günter_Hotz
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hadamard_code
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hedonic_game
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Irit_Dinur
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:field
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Joachim_von_zur_Gathen
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Julia_Robinson
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Jungle_Disk
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Juraj_Hromkovič
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Karloff–Zwick_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Karp's_21_NP-complete_problems
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Larry_Stockmeyer
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:knownFor
dbr:Computational_complexity_theory
Subject Item
dbr:Leaf_language
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Linear_bounded_automaton
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Linear_search_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Linear_speedup_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_decoding
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_Carnegie_Mellon_University_people
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_Columbia_University_people
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Locally_decodable_code
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Log-space_computable_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Log-space_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Log-space_transducer
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Polynomial-time_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Security_of_cryptographic_hash_functions
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:P-complete
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sherman–Morrison_formula
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:TFNP
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Toniann_Pitassi
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Two-variable_logic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Potential_method
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Wadge_hierarchy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Promise_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:20th_century_in_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:3SUM
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:A*_search_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:AKS_primality_test
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Abstract_data_type
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Adi_Shamir
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Alexander_Razborov
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Algebraic_geometry
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Allan_Borodin
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Anatol_Slissenko
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Alain_A._Lewis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:DFA_minimization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dana_Scott
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Daniel_J._Hulme
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:ELEMENTARY
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:EXPTIME
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:E_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Alternating_Turing_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Eric_Allender
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ernst_Mayr_(computer_scientist)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Euclidean_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Expander_graph
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Felipe_Cucker
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Field_with_one_element
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:First-order_logic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Anil_Nerode
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Bao_(game)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Nikolai_Sergeevich_Bakhvalov
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:knownFor
dbr:Computational_complexity_theory
dbo:knownFor
dbr:Computational_complexity_theory
Subject Item
dbr:Nitin_Saxena
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Noam_Nisan
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Number_sign
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Number_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Oscar_H._Ibarra
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:knownFor
dbr:Computational_complexity_theory
Subject Item
dbr:PP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PSPACE
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Carl_Herbert_Smith
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dimensionality_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dimiter_Skordev
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Discretization_error
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Edith_Hemaspaandra
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Fast-growing_hierarchy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Fast_Fourier_transform
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Fast_Walsh–Hadamard_transform
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Floyd–Warshall_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Formal_language
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Formula_game
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Foundations_of_mathematics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Four_color_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Fragment_(logic)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Goertzel_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Graph_automorphism
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Graph_canonization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Graph_isomorphism
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hilbert_series_and_Hilbert_polynomial
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:History_of_computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:History_of_logic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:History_of_mathematics
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:History_of_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Isolation_lemma
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Isoperimetric_inequality
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Isotonic_regression
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Iterated_logarithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:John_Reif
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Journey_planner
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Judy_Goldsmith_(computer_scientist)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Karatsuba_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Knuth–Morris–Pratt_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Unary_numeral_system
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_Massachusetts_Institute_of_Technology_alumni
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_Russian_IT_developers
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Robert_P._Dilworth
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Randomness_extractor
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Gap_theorem_(disambiguation)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Michael_J._Fischer
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pseudorandom_number_generator
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hard_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Profiling_(computer_programming)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Provable_security
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:QIP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Quadratic_residuosity_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Query_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:RE_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:RL_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:R_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Rectilinear_polygon
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Reduction_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Regular_language
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:2-EXPTIME
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:2-satisfiability
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Gödel's_incompleteness_theorems
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Handshaking_lemma
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Harry_R._Lewis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hash_table
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Heidelberg_University_Faculty_of_Mathematics_and_Computer_Science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Helmut_Veith
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Herbert_Enderton
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Heyting_algebra
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Asymptotic_computational_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Atomix_(video_game)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Jaroslav_Nešetřil
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Jean-Paul_Delahaye
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:fields
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Jeff_Edmonds
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Jelani_Nelson
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:BPL_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Counting_problem_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Tetris
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hungarian_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hypohamiltonian_graph
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Jin-Yi_Cai
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Marek_Karpinski
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pebble_game
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Toda's_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Speed_prior
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:State_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ashok_K._Chandra
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:AI-complete
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:ALL_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:APX
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:A_New_Kind_of_Science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Abstract_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ackermann_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Advantage_(cryptography)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Advice_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Charles_Rackoff
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Chennai_Mathematical_Institute
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Johan_Håstad
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Johann_Makowsky
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Juris_Hartmanis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Karp–Lipton_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Lambda_calculus
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Lance_Fortnow
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Lasse_Rempe
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Big_O_notation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Billion_laughs_attack
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Blossom_tree_(graph_theory)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Superhuman
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:TUM_School_of_Computation,_Information_and_Technology
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Co-NP-complete
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Cobham's_thesis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Cognitive_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Effective_results_in_number_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Efficient_Probabilistic_Public-Key_Encryption_Scheme
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:George_Sugihara
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hessenberg_matrix
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Hex_(board_game)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Heyawake
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Holographic_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Tractable_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Stathis_Zachos
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Wilson's_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:ZPP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Pseudorandom_generator_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Read-only_Turing_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Reduction_(computability_theory)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Samuel_Buss
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dima_Grigoriev
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Dominating_set
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Arthur–Merlin_protocol
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Automatic_differentiation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Average-case_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Averaging_argument
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Manuel_Blum
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Mario_Szegedy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Marketing_mix
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Martin_Vetterli
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Boolean_circuit
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Boolean_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Boolean_satisfiability_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Boson_sampling
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:CC_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:CTL*
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:CURE_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Philip_Mirowski
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Philippe_Flajolet
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Polynomial
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Polynomial_hierarchy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PostBQP
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sokoban
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sorting_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Square_root
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Circuit_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Circuits_over_sets_of_natural_numbers
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:File_carving
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Fine-grained_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Group_testing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ian_Sloan_(mathematician)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Implicit_graph
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:In-place_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Algorithmic_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Kurt_Mehlhorn
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Micah_Altman
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Michael_Fellows
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Michael_O._Rabin
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Michael_Sipser
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Mihalis_Yannakakis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Miklós_Ajtai
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:fields
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:National_Kidney_Registry
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Natural_logarithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Network-centric_warfare
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Oded_Goldreich
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Cascaded_integrator–comb_filter
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:RP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:RSA_(cryptosystem)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ran_Raz
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:fields
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Randomized_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Certificate_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Chandy–Misra–Haas_algorithm_resource_model
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Search_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Second-order_logic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sergei_Evdokimov
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Shafi_Goldwasser
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sheila_Greibach
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Klaus_Sutner
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Klee's_measure_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Loop_variant
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Minimax
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Model_of_computation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Model_order_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Multidisciplinary_design_optimization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Multiple_sequence_alignment
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Turing_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Routing_(electronic_design_automation)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:SC_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:SNP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Satisfiability
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Search-based_software_engineering
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Set_cover_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Shmuel_Safra
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:field
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Sihem_Amer-Yahia
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sim_(pencil_game)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Skolem_arithmetic
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:UP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Umesh_Vazirani
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:fields
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Undecidable_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Unique_games_conjecture
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Universal_Turing_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Victor_Vianu
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Vijay_Vazirani
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:fields
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Wallace_tree
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Negligible_function
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Random-access_Turing_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Uwe_Schöning
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Victor_Anatolyevich_Vassiliev
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sharp-SAT
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Exponential_growth
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Exponential_hierarchy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Exponential_time_hypothesis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Extremal_graph_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:FL_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:FNP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:FORK-256
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:FP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Fagin's_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_(disambiguation)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageDisambiguates
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageDisambiguates
dbr:Computational_complexity_theory
Subject Item
dbr:IMU_Abacus_Medal
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:IP_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Immerman–Szelepcsényi_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Implicit_computational_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:In_Pursuit_of_the_Traveling_Salesman
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:List_of_theorems
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Neeraj_Kayal
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Subhash_Khot
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Low_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Planted_clique
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Self-stabilization
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ruzsa–Szemerédi_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Thomas_Jerome_Schaefer
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Exact_quantum_polynomial_time
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Existential_theory_of_the_reals
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:First-order_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Malware_research
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:N-body_simulation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NEXPTIME
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NP-completeness
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NP-equivalent
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NP-hardness
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NP-intermediate
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
n14:poly
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NSPACE
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NTIME
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Natural_computing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Natural_proof
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sequence_container_(C++)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Vertex_enumeration_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Schnorr_signature
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:The_Complexity_of_Songs
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:NL-complete
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Robert_B._Lisek
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Motion_planning
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Multilayer_perceptron
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Multitape_Turing_machine
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Multitree
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Science_and_technology_in_Venezuela
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:PolyL
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Polynomial-time_counting_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Polynomial_creativity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Polynomial_evaluation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Social_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Unary_language
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Stanisław_Radziszowski
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Series–parallel_graph
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Switching_lemma
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Transcomputational_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Time_hierarchy_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Turing_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Nondeterministic_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Nonelementary_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Scalability
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ultrafinitism
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Product_planning
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Transdichotomous_model
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Peptide_computing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Set_packing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Savitch's_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Outline_of_academic_disciplines
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Outline_of_computer_programming
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Outline_of_computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Outline_of_formal_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Outline_of_software_engineering
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:P_versus_NP_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Panama_(cryptography)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Parallel_computation_thesis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Parallel_multidimensional_digital_signal_processing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Parameterized_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Peter_Bossaerts
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Semantic_compression
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Property_testing
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sum_of_radicals
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Word_chain
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Slowsort
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Set_splitting_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Slow-growing_hierarchy
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:True_quantified_Boolean_formula
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Random_oracle
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ransomware
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:UBC_Department_of_Computer_Science
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:S2P_(complexity)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Yao's_principle
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Sipser–Lautemann_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Structural_complexity_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Two-way_finite_automaton
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Ronald_de_Wolf
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Xi_Chen
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbp:knownFor
dbr:Computational_complexity_theory
dbo:knownFor
dbr:Computational_complexity_theory
Subject Item
dbr:Stefan_Szeider
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:academicDiscipline
dbr:Computational_complexity_theory
Subject Item
dbr:Feasible_computability
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Feasible_computation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Intractable_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Intractableness
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Intractably
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Speedup_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
Subject Item
dbr:Order_of_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Order_of_computation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Levin_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Calculation_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Continuous_complexity_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Hierarchy_theorem
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_of_algorithms
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_theory_(computation)
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Complexity_theory_in_computation
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_complexity_analysis
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Computational_intractability
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Computationally_infeasible
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Computationally_intractable
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
dbr:Space_complexity_theory
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory
dbo:wikiPageRedirects
dbr:Computational_complexity_theory
Subject Item
wikipedia-en:Computational_complexity_theory
foaf:primaryTopic
dbr:Computational_complexity_theory