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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n12https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_algorithm_general_topics
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:List_of_complexity_classes
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:List_of_computability_and_complexity_topics
rdfs:label
List of computability and complexity topics
rdfs:comment
This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard computations are, in quantitative terms, both with upper bounds (algorithms whose complexity in the worst cases, as use of computing resources, can be estimated), and from below (proofs that no procedure to carry out some task can be very fast).
dcterms:subject
dbc:Wikipedia_outlines dbc:Theory_of_computation dbc:Outlines_of_mathematics_and_logic dbc:Complexity_classes dbc:Mathematics-related_lists
dbo:wikiPageID
353748
dbo:wikiPageRevisionID
1095686803
dbo:wikiPageWikiLink
dbr:Turing_tarpit dbr:Deterministic_Turing_machine dbr:Recursion_(computer_science) dbr:Interactive_computation dbr:Time_hierarchy_theorem dbr:Real_computation dbr:Exponentiating_by_squaring dbr:Probabilistic_Turing_Machine dbr:2-satisfiability dbr:Parameterized_complexity dbr:Quantum_computer dbr:Independent_set_problem dbr:Knapsack_problem dbr:Entscheidungsproblem dbr:Interactive_proof_system dbr:Regular_language dbr:Game_semantics dbr:Subset_sum_problem dbr:Recursion dbr:Polynomial-time_Turing_reduction dbr:Definable_number dbr:Advice_(complexity) dbr:Flynn's_taxonomy dbr:Non-deterministic_Turing_machine dbr:Non-determinism_(disambiguation) dbr:Halting_problem dbr:Decidable_language dbr:Set_cover_problem dbc:Wikipedia_outlines dbr:Process_calculi dbr:Arithmetic_circuit_complexity dbr:State_diagram dbr:Petri_net dbr:Linear_time dbr:Polynomial_hierarchy dbr:Cook's_theorem dbr:Integer_factorization dbr:Multiplication_table dbr:Computational_complexity_theory dbr:Computation dbr:Multiplication_algorithm dbr:Lambda_calculus dbr:B,_C,_K,_W_System dbr:Context-free_grammar dbr:Term_rewriting dbr:Computability_theory dbr:Büchi_automaton dbr:Combinatory_logic dbr:Savitch's_theorem dbr:Generating_trigonometric_tables dbr:Rewriting dbr:Busy_beaver dbr:Pi-calculus dbr:Generalized_nondeterministic_finite_automaton dbr:Arthur–Merlin_protocol dbr:Natural_proof dbc:Theory_of_computation dbr:Ant_colony_algorithm dbr:Hamiltonian_cycle_problem dbr:Regular_expression dbr:One_way_function dbr:Turing_machine dbr:Lookup_table dbr:Chomsky_hierarchy dbr:Subroutine dbr:Peasant_multiplication dbr:List_of_algorithm_general_topics dbr:Weihrauch_reducibility dbr:Post–Turing_machine dbr:Halting_probability dbr:List_of_complexity_classes dbr:List_of_algorithms dbr:Presburger_arithmetic dbr:Computable_number dbr:Moore_machine dbr:Computable_analysis dbr:Register_machine dbr:Combinator dbr:Probabilistic_algorithm dbr:Generalized_game dbr:Finite_state_automaton dbr:Turing-complete dbr:Hypercomputation dbr:Post_correspondence_problem dbr:Alternating_automaton dbr:Knuth–Bendix_completion_algorithm dbr:Alternating_Turing_machine dbr:Algorithmic_probability dbr:Cellular_automaton dbr:Constructible_function dbr:Speed_Prior dbr:Calculation dbr:Rule_110_cellular_automaton dbr:Star_height_problem dbr:Subquadratic_time dbr:Boolean_satisfiability_problem dbr:Mathematical_table dbr:Traveling_salesman_problem dbr:Conway's_Game_of_Life dbr:Division_by_two dbr:Function_problem dbr:Stack_machine dbr:Pushdown_automaton dbr:Penrose_tiling dbr:Myhill-Nerode_theorem dbr:Tree_automaton dbr:Amortized_analysis dbr:Oracle_machine dbr:Church-Turing_thesis dbr:Linear_speedup_theorem dbr:3SUM dbr:Multiple-agent_system dbr:Wang_tile dbr:Satisfiability_problem dbr:Algorithm dbr:Universal_quantum_computer dbr:Deterministic_finite_automaton dbr:L-system dbr:Edge_of_chaos dbr:Polynomial_time dbr:Mealy_machine dbr:Algorithmic_information_theory dbr:Recursively_enumerable_language dbr:Las_Vegas_algorithm dbr:Minsky_register_machine dbr:Scholz_conjecture dbr:Decision_problem dbc:Outlines_of_mathematics_and_logic dbr:History_of_computers dbr:Pumping_lemma dbr:Randomized_algorithm dbr:Approximation_algorithm dbr:Simulated_annealing dbr:Exponential_time dbc:Complexity_classes dbr:Clique_problem dbr:Vertex_cover_problem dbr:String_rewriting_system dbc:Mathematics-related_lists dbr:Context-sensitive_grammar dbr:Best_and_worst_cases dbr:Addition_chain dbr:Context-sensitive_language dbr:Hamiltonian_path_problem dbr:Data_compression dbr:Prefix_grammar dbr:Word_problem_for_groups dbr:Star_height dbr:Parallel_computing dbr:Markov_algorithm dbr:Generalized_star_height_problem dbr:Polynomial-time_many-one_reduction dbr:Langton's_ant dbr:Regular_grammar dbr:Undecidable_language dbr:Exponential_hierarchy dbr:Nondeterministic_finite_automaton dbr:Space_hierarchy_theorem dbr:State_transition_system dbr:List_of_mathematical_logic_topics dbr:Circuit_complexity dbr:Correctness_(computer_science)
owl:sameAs
n12:4qPLr wikidata:Q6613099
dbp:wikiPageUsesTemplate
dbt:Short_description
dbo:abstract
This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard computations are, in quantitative terms, both with upper bounds (algorithms whose complexity in the worst cases, as use of computing resources, can be estimated), and from below (proofs that no procedure to carry out some task can be very fast). For more abstract foundational matters, see the list of mathematical logic topics. See also list of algorithms, list of algorithm general topics.
gold:hypernym
dbr:List
prov:wasDerivedFrom
wikipedia-en:List_of_computability_and_complexity_topics?oldid=1095686803&ns=0
dbo:wikiPageLength
5209
foaf:isPrimaryTopicOf
wikipedia-en:List_of_computability_and_complexity_topics
Subject Item
dbr:List_of_mathematical_logic_topics
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:Mathematical_logic
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:MAXEkSAT
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:Computational_complexity_theory
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:Lists_of_mathematics_topics
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:List_of_computability_&_complexity_topics
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageRedirects
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:Outline_of_complexity
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageRedirects
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:Outline_of_complexity_and_computability
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageRedirects
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:Outline_of_computability
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageRedirects
dbr:List_of_computability_and_complexity_topics
Subject Item
dbr:Outline_of_computability_and_complexity
dbo:wikiPageWikiLink
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageRedirects
dbr:List_of_computability_and_complexity_topics
Subject Item
wikipedia-en:List_of_computability_and_complexity_topics
foaf:primaryTopic
dbr:List_of_computability_and_complexity_topics