About: Computational complexity theory

Property	Value
rdf:type	skos:Concept
rdfs:label	Computational complexity theory
skos:broader	dbpedia:Category:Theoretical_computer_science
skos:prefLabel	Computational complexity theory
is skos:broader of	dbpedia:Category:Analysis_of_algorithms dbpedia:Category:Computational_hardness_assumptions dbpedia:Category:Probabilistic_complexity_theory dbpedia:Category:Circuit_complexity dbpedia:Category:Structural_complexity_theory dbpedia:Category:Computational_resources dbpedia:Category:Quantum_complexity_theory
is skos:subject of	dbpedia:Complexity dbpedia:Computational_complexity_theory dbpedia:Quantum_computer dbpedia:Approximation_algorithm dbpedia:Accounting_method dbpedia:Descriptive_complexity_theory dbpedia:Log-space_reduction dbpedia:Gap_theorem dbpedia:Asymptotic_computational_complexity dbpedia:Computational_resource dbpedia:Computational_topology dbpedia:Constructible_function dbpedia:Context_of_computational_complexity dbpedia:DNA_Dynamics dbpedia:Generalized_game dbpedia:L-notation dbpedia:Molecular_models_of_DNA dbpedia:Many-one_reduction dbpedia:Interactive_proof_system dbpedia:Cook–Levin_theorem dbpedia:Complete_(complexity) dbpedia:Almost_complete dbpedia:Averaging_argument dbpedia:Exponential_time dbpedia:Low_(complexity) dbpedia:PCP_theorem dbpedia:L-reduction dbpedia:Karp-Lipton_theorem dbpedia:Kernelization dbpedia:Kolmogorov_structure_function dbpedia:Leaf_language dbpedia:Linearithmic_function dbpedia:Multilinear_polynomial dbpedia:Polynomial_time dbpedia:Nondeterministic_algorithm dbpedia:Polynomial-time_reduction dbpedia:Pseudo-polynomial_time dbpedia:Universal_hashing dbpedia:(SAT,_ε-UNSAT) dbpedia:Analysis_of_algorithms dbpedia:Blum's_speedup_theorem dbpedia:Constant_time dbpedia:Proof_complexity dbpedia:Communication_complexity dbpedia:Computing_the_permanent dbpedia:Gadget_(computer_science) dbpedia:Hardness_of_approximation dbpedia:Information-based_complexity dbpedia:Introduction_to_the_Theory_of_Computation dbpedia:Linear_speedup_theorem dbpedia:List-decoding dbpedia:Minimum_weight_triangulation dbpedia:Negational_normal_form dbpedia:Reduction_(complexity) dbpedia:Combinatorial_optimization dbpedia:Complexity_class dbpedia:Parameterized_complexity dbpedia:Speedup_theorem dbpedia:Best,_worst_and_average_case dbpedia:AI-complete dbpedia:Advice_(complexity) dbpedia:Asymptotically_optimal_algorithm dbpedia:Boolean_circuit dbpedia:Certificate_(complexity) dbpedia:Circuit_complexity dbpedia:Cobham's_thesis dbpedia:Complement_(complexity) dbpedia:Complexity_index dbpedia:Compression_theorem dbpedia:Computation_tree dbpedia:Computational_complexity_of_mathematical_operations dbpedia:Decision_tree_complexity dbpedia:Decision_tree_model dbpedia:Interval-valued_computation dbpedia:Natural_proof dbpedia:PTAS_reduction dbpedia:Proper_complexity_function dbpedia:Randomness_extractor dbpedia:Sub-exponential_time dbpedia:Uniformity_(complexity) dbpedia:Pebble_game dbpedia:Sublinear_time_algorithm dbpedia:Truth_table_reduction dbpedia:Yao's_principle dbpedia:Pseudorandom_generator_theorem dbpedia:Smoothed_analysis dbpedia:Sparse_language dbpedia:Symmetric_Turing_machine dbpedia:The_Complexity_of_Songs dbpedia:Unary_language dbpedia:Schaefer's_dichotomy_theorem dbpedia:Turing_reduction