Browse using
OpenLink Faceted Browser
OpenLink Structured Data Editor
LodLive Browser
Formats
RDF:
N-Triples
N3
Turtle
JSON
XML
OData:
Atom
JSON
Microdata:
JSON
HTML
Embedded:
JSON
Turtle
Other:
CSV
JSON-LD
Faceted Browser
Sparql Endpoint
About:
Computational complexity theory
An Entity of Type:
Concept
,
from Named Graph:
http://dbpedia.org
,
within Data Space:
dbpedia.org
Property
Value
dbo:
wikiPageID
693727
(xsd:integer)
dbo:
wikiPageRevisionID
969858777
(xsd:integer)
dbp:
wikiPageUsesTemplate
dbt
:Commons_category
dbt
:CatAutoTOC
dbt
:Cat_main
rdf:
type
skos
:Concept
rdfs:
label
Computational complexity theory
(en)
skos:
broader
dbc
:Computational_fields_of_study
dbc
:Complex_systems_theory
dbc
:Theory_of_computation
skos:
prefLabel
Computational complexity theory
(en)
prov:
wasDerivedFrom
wikipedia-en
:Category:Computational_complexity_theory?oldid=969858777&ns=14
is
dbo:
wikiPageWikiLink
of
dbr
:Proof_(truth)
dbr
:Proof_complexity
dbr
:Pseudo-polynomial_transformation
dbr
:Quantum_complexity_theory
dbr
:Electronic_Colloquium_on_Computational_Complexity
dbr
:Randomness_merger
dbr
:Strong_NP-completeness
dbr
:Approximation_algorithm
dbr
:Best,_worst_and_average_case
dbr
:Decision_tree_model
dbr
:Descriptive_complexity_theory
dbr
:Dynamic_problem_(algorithms)
dbr
:Information-based_complexity
dbr
:Integer_circuit
dbr
:Interactive_proof_system
dbr
:Introduction_to_the_Theory_of_Computation
dbr
:L-notation
dbr
:Quantum_computing
dbr
:Proof_of_knowledge
dbr
:Proper_complexity_function
dbr
:Propositional_proof_system
dbr
:Pseudo-polynomial_time
dbr
:Complexity_index
dbr
:Computational_complexity_of_matrix_multiplication
dbr
:Computing_the_permanent
dbr
:Analysis_of_algorithms
dbr
:Generalized_game
dbr
:Generic-case_complexity
dbr
:Geometric_complexity_theory
dbr
:Low-complexity_art
dbr
:Non-constructive_algorithm_existence_proofs
dbr
:Quantum_capacity
dbr
:Glossary_of_quantum_computing
dbr
:Configuration_graph
dbr
:Constructible_function
dbr
:Bernstein–Vazirani_algorithm
dbr
:Claw_finding_problem
dbr
:Combinatorial_optimization
dbr
:Combinatorial_search
dbr
:Communication_complexity
dbr
:Complement_(complexity)
dbr
:Complete_(complexity)
dbr
:Complexity_and_Real_Computation
dbr
:Complexity_class
dbr
:Compression_theorem
dbr
:Computable_topology
dbr
:Computation_tree
dbr
:Computational_complexity
dbr
:Computational_complexity_of_mathematical_operations
dbr
:Computational_complexity_theory
dbr
:Computational_resource
dbr
:Computational_topology
dbr
:Computationally_bounded_adversary
dbr
:Half-exponential_function
dbr
:Hamiltonian_complexity
dbr
:Hardness_of_approximation
dbr
:Padding_argument
dbr
:Mahaney's_theorem
dbr
:Quantum_supremacy
dbr
:Sparse_language
dbr
:Time_complexity
dbr
:Games,_Puzzles,_and_Computation
dbr
:Gap-Hamming_problem
dbr
:Leaf_language
dbr
:List_decoding
dbr
:Log-rank_conjecture
dbr
:Log-space_computable_function
dbr
:Log-space_transducer
dbr
:Logical_depth
dbr
:Folded_Reed–Solomon_code
dbr
:Graph_isomorphism_problem
dbr
:Kolmogorov_complexity
dbr
:Lempel–Ziv_complexity
dbr
:Randomness_extractor
dbr
:Asymptotic_computational_complexity
dbr
:Pebble_game
dbr
:Smoothed_analysis
dbr
:Aanderaa–Karp–Rosenberg_conjecture
dbr
:Advice_(complexity)
dbr
:Cobham's_thesis
dbr
:Effective_complexity
dbr
:Hidden_linear_function_problem
dbr
:Tractable_problem
dbr
:Averaging_argument
dbr
:Boolean_circuit
dbr
:Circuit_complexity
dbr
:Circuits_over_sets_of_natural_numbers
dbr
:Klee–Minty_cube
dbr
:Certificate_(complexity)
dbr
:Model_of_computation
dbr
:Unique_games_conjecture
dbr
:Implicit_computational_complexity
dbr
:Low_(complexity)
dbr
:Symmetric_Turing_machine
dbr
:Exact_algorithm
dbr
:Existential_theory_of_the_reals
dbr
:Universal_hashing
dbr
:Weak_NP-completeness
dbr
:Natural_proof
dbr
:The_Complexity_of_Songs
dbr
:Unary_language
dbr
:Switching_lemma
dbr
:Transcomputational_problem
dbr
:Noisy_intermediate-scale_quantum_era
dbr
:Nondeterministic_algorithm
dbr
:Semi-membership
dbr
:Transdichotomous_model
dbr
:Parameterized_complexity
dbr
:Yao's_principle
dbr
:Space_complexity
is
dcterms:
subject
of
dbr
:Proof_(truth)
dbr
:Proof_complexity
dbr
:Pseudo-polynomial_transformation
dbr
:Quantum_complexity_theory
dbr
:Electronic_Colloquium_on_Computational_Complexity
dbr
:Randomness_merger
dbr
:Strong_NP-completeness
dbr
:Approximation_algorithm
dbr
:Best,_worst_and_average_case
dbr
:Decision_tree_model
dbr
:Descriptive_complexity_theory
dbr
:Dynamic_problem_(algorithms)
dbr
:Information-based_complexity
dbr
:Integer_circuit
dbr
:Interactive_proof_system
dbr
:Introduction_to_the_Theory_of_Computation
dbr
:L-notation
dbr
:Quantum_computing
dbr
:Proof_of_knowledge
dbr
:Proper_complexity_function
dbr
:Propositional_proof_system
dbr
:Pseudo-polynomial_time
dbr
:Complexity_index
dbr
:Computational_complexity_of_matrix_multiplication
dbr
:Computing_the_permanent
dbr
:Analysis_of_algorithms
dbr
:Generalized_game
dbr
:Generic-case_complexity
dbr
:Geometric_complexity_theory
dbr
:Low-complexity_art
dbr
:Non-constructive_algorithm_existence_proofs
dbr
:Quantum_capacity
dbr
:Glossary_of_quantum_computing
dbr
:Configuration_graph
dbr
:Constructible_function
dbr
:Bernstein–Vazirani_algorithm
dbr
:Claw_finding_problem
dbr
:Combinatorial_optimization
dbr
:Combinatorial_search
dbr
:Communication_complexity
dbr
:Complement_(complexity)
dbr
:Complete_(complexity)
dbr
:Complexity_and_Real_Computation
dbr
:Complexity_class
dbr
:Compression_theorem
dbr
:Computable_topology
dbr
:Computation_tree
dbr
:Computational_complexity
dbr
:Computational_complexity_of_mathematical_operations
dbr
:Computational_complexity_theory
dbr
:Computational_resource
dbr
:Computational_topology
dbr
:Computationally_bounded_adversary
dbr
:Half-exponential_function
dbr
:Hamiltonian_complexity
dbr
:Hardness_of_approximation
dbr
:Padding_argument
dbr
:Mahaney's_theorem
dbr
:Quantum_supremacy
dbr
:Sparse_language
dbr
:Time_complexity
dbr
:Games,_Puzzles,_and_Computation
dbr
:Gap-Hamming_problem
dbr
:Leaf_language
dbr
:List_decoding
dbr
:Log-rank_conjecture
dbr
:Log-space_computable_function
dbr
:Log-space_transducer
dbr
:Logical_depth
dbr
:Folded_Reed–Solomon_code
dbr
:Graph_isomorphism_problem
dbr
:Kolmogorov_complexity
dbr
:Lempel–Ziv_complexity
dbr
:Randomness_extractor
dbr
:Asymptotic_computational_complexity
dbr
:Pebble_game
dbr
:Smoothed_analysis
dbr
:Aanderaa–Karp–Rosenberg_conjecture
dbr
:Advice_(complexity)
dbr
:Cobham's_thesis
dbr
:Effective_complexity
dbr
:Hidden_linear_function_problem
dbr
:Tractable_problem
dbr
:Averaging_argument
dbr
:Boolean_circuit
dbr
:Circuit_complexity
dbr
:Circuits_over_sets_of_natural_numbers
dbr
:Klee–Minty_cube
dbr
:Certificate_(complexity)
dbr
:Model_of_computation
dbr
:Unique_games_conjecture
dbr
:Implicit_computational_complexity
dbr
:Low_(complexity)
dbr
:Symmetric_Turing_machine
dbr
:Exact_algorithm
dbr
:Existential_theory_of_the_reals
dbr
:Universal_hashing
dbr
:Weak_NP-completeness
dbr
:Natural_proof
dbr
:The_Complexity_of_Songs
dbr
:Unary_language
dbr
:Switching_lemma
dbr
:Transcomputational_problem
dbr
:Noisy_intermediate-scale_quantum_era
dbr
:Nondeterministic_algorithm
dbr
:Semi-membership
dbr
:Transdichotomous_model
dbr
:Parameterized_complexity
dbr
:Yao's_principle
dbr
:Space_complexity
is
skos:
broader
of
dbc
:Quantum_computing
dbc
:Reduction_(complexity)
dbc
:NP-complete_problems
dbc
:Structural_complexity_theory
dbc
:Theorems_in_computational_complexity_theory
dbc
:Computational_hardness_assumptions
dbc
:Computational_resources
dbc
:Strongly_NP-complete_problems
dbc
:Complexity_classes
dbc
:Circuit_complexity
dbc
:Computational_problems
dbc
:Quantum_complexity_theory
dbc
:Analysis_of_algorithms
dbc
:Parameterized_complexity
dbc
:Descriptive_complexity
This content was extracted from
Wikipedia
and is licensed under the
Creative Commons Attribution-ShareAlike 3.0 Unported License