About: Word problem (computability)

Property	Value
dbo:description	qüestió en un sistema formal amb resposta sí o no (ca) otázka s odpovědí ano-ne (cs) persoalan menentukan keputusan (mis. ya/tidak) (in) tipo di problema computazionale (it) yes/no problem in computer science (en)
dbo:thumbnail	wiki-commons:Special:FilePath/Decision_Problem.svg?width=300
dbo:wikiPageExternalLink	https://www.google.com/books/edition/Decision_Procedures/SaUywbXY9C8C%3Fhl=en&pg=PR1 https://www.google.com/books/edition/Recursively_Enumerable_Sets_and_Degrees/9I7Pl00LU5gC%3Fhl=en&pg=PP1 https://www.google.com/books/edition/The_Calculus_of_Computation/0MbX7xVpffAC%3Fhl=en&pg=PR2 https://books.google.com/books%3Fid=Vo3fBwAAQBAJ&q=%22decision+problem%22
dbo:wikiPageWikiLink	dbr:Search_problem dbr:ALL_(complexity) dbr:Decidability_(logic) dbr:List_of_undecidable_problems dbr:Polynomial-time_reduction dbr:Effective_method dbr:Prime dbr:Word_problem_(mathematics) dbc:Computability_theory dbr:Algorithm dbr:Computational_resource dbr:Yes–no_question dbc:Computational_problems dbr:Computational_complexity_theory dbr:Formal_language dbr:Boolean_satisfiability_problem dbr:Complexity_class dbr:Halting_problem dbr:Gödel_numbering dbr:String_(computer_science) dbr:Indicator_function dbr:Linear_programming dbr:Counting_problem_(complexity) dbr:NP_(complexity) dbr:Infinite_set dbr:Operations_research dbr:Complement_(complexity) dbr:Computational_problem dbr:Computability_theory dbr:Long_division dbr:Turing_degree dbr:Partial_function dbr:Function_problem dbr:Co-NP-complete dbr:Polynomial_time dbr:Many-one_reduction dbr:Undecidable_problem dbr:Traveling_salesman_problem dbr:NP-complete dbr:Recursively_enumerable_set dbr:Recursive_set dbr:Recursion_theory dbr:Alphabet_(computer_science) dbr:Logical_theory dbr:Complete_problem dbr:Primality_testing dbr:File:Decision_Problem.svg
dbp:group	notes (en)
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Mathematical_logic dbt:About dbt:Authority_control dbt:Main dbt:Reflist dbt:Short_description
dct:subject	dbc:Computability_theory dbc:Computational_problems
gold:hypernym	dbr:Question
rdf:type	owl:Thing owl:Thing
rdfs:label	Word problem (computability) (en) Decision problem (en) Rozhodovací problém (cs) Problema de decisió (ca) Πρόβλημα απόφασης (el) Entscheidungsproblem (de) Decidoproblemo (eo) Problema de decisión (es) Problème de décision (fr) Problema decisionale (it) 決定問題 (ja) 결정 문제 (ko) Beslissingsprobleem (nl) Problema de decisão (pt) Problem decyzyjny (teoria obliczeń) (pl) Задача вибору (uk) Задача разрешимости (ru) Beslutsproblem (sv) 決定性問題 (zh)
owl:sameAs	freebase:Word problem (computability) yago-res:Word problem (computability) wikidata:Word problem (computability) dbpedia-de:Word problem (computability) dbpedia-es:Word problem (computability) dbpedia-it:Word problem (computability) dbpedia-nl:Word problem (computability) dbpedia-pl:Word problem (computability) dbpedia-fr:Word problem (computability) dbpedia-he:Word problem (computability) dbpedia-ja:Word problem (computability) dbpedia-pt:Word problem (computability) dbpedia-ru:Word problem (computability) dbpedia-zh:Word problem (computability) dbpedia-sv:Word problem (computability) dbpedia-el:Word problem (computability) dbpedia-ko:Word problem (computability) dbpedia-ca:Word problem (computability) dbpedia-bn:Word problem (computability) dbpedia-cs:Word problem (computability) dbpedia-eo:Word problem (computability) dbpedia-fa:Word problem (computability) dbpedia-hr:Word problem (computability) dbpedia-hy:Word problem (computability) dbpedia-kn:Word problem (computability) dbpedia-sh:Word problem (computability) dbpedia-simple:Word problem (computability) dbpedia-sr:Word problem (computability) dbpedia-th:Word problem (computability) dbpedia-uk:Word problem (computability) dbpedia-global:Word problem (computability)
prov:wasDerivedFrom	wikipedia-en:Decision_problem?oldid=1291139298&ns=0 wikipedia-en:Word_problem_(computability)?oldid=415138287&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Decision_Problem.svg
foaf:isPrimaryTopicOf	wikipedia-en:Word_problem_(computability) wikipedia-en:Decision_problem
is dbo:wikiPageRedirects of	dbr:Word_problem_(computability) dbr:Word_problem_(computability) dbr:Decidable_problem dbr:Solvable_problem dbr:Decidability_problems dbr:Decision_problems dbr:Decision_procedure dbr:Decision_variant dbr:Decision_version
is dbo:wikiPageWikiLink of	dbr:Search_problem dbr:Principles_of_Mathematical_Logic dbr:ALL_(complexity) dbr:L-reduction dbr:Decidability_(logic) dbr:History_of_group_theory dbr:Semantics dbr:Exact_cover dbr:Rice's_theorem dbr:Co-NP dbr:Complete_coloring dbr:Domatic_number dbr:Circuit_satisfiability_problem dbr:Computability dbr:Kernelization dbr:NP-equivalent dbr:Polynomial-time_reduction dbr:Longest_path_problem dbr:Effective_method dbr:FP_(complexity) dbr:Recursive_language dbr:Mortality_(computability_theory) dbr:Static_program_analysis dbr:Art_gallery_problem dbr:Word_problem_(mathematics) dbr:Differentiable_manifold dbr:Ian_Horrocks dbr:Bin_packing_problem dbr:DSPACE dbr:DTIME dbr:Subset_sum_problem dbr:List_of_knapsack_problems dbr:Word_problem_for_groups dbr:Alan_Turing dbr:Mathematical_logic dbr:Turing's_proof dbr:Turing_reduction dbr:Combinatorial_optimization dbr:Greatest_common_divisor dbr:Monochromatic_triangle dbr:Schaefer's_dichotomy_theorem dbr:Clique_cover dbr:Logic_of_graphs dbr:Parametric_search dbr:Planted_clique dbr:Yes–no_question dbr:NSPACE dbr:Exact_quantum_polynomial_time dbr:Residue-class-wise_affine_group dbr:PSPACE dbr:Saul_Kripke dbr:Computational_complexity_theory dbr:Formal_language dbr:Graph_theory dbr:Mastermind_(board_game) dbr:Model_checking dbr:Property_testing dbr:Metamathematics dbr:Type_theory dbr:Square-free_integer dbr:Hans_Hermes dbr:Minimum_spanning_tree dbr:Boolean_satisfiability_problem dbr:Knapsack_problem dbr:Promise_problem dbr:Raphael_M._Robinson dbr:CC_(complexity) dbr:Closest_string dbr:Digi-Comp_II dbr:Set_packing dbr:Expression_(mathematics) dbr:Monte_Carlo_algorithm dbr:Weighted_majority_algorithm_(machine_learning) dbr:Robert_Shostak dbr:Group_isomorphism_problem dbr:Interior_algebra dbr:BPP_(complexity) dbr:Depth-first_search dbr:Complexity_class dbr:Graph_minor dbr:Independence_(mathematical_logic) dbr:Halting_problem dbr:Levi's_lemma dbr:Type_system dbr:Tracing_garbage_collection dbr:Hedonic_game dbr:Approximation-preserving_reduction dbr:Equivalence_problem dbr:Gödel's_incompleteness_theorems dbr:Wilhelm_Ackermann dbr:Unit_testing dbr:History_of_computing_hardware dbr:P_versus_NP_problem dbr:Integer_factorization dbr:Maximum_cut dbr:Feedback_vertex_set dbr:Solovay–Strassen_primality_test dbr:Steiner_tree_problem dbr:Hamiltonian_completion dbr:Courcelle's_theorem dbr:Vertex_cover dbr:Optimization_problem dbr:Satisfiability dbr:NTIME dbr:Word_problem_(computability) dbr:FNP_(complexity) dbr:Minimum-cost_flow_problem dbr:Hierarchy_(mathematics) dbr:Boolean_algebra dbr:Genetic_algorithm dbr:Lambda_calculus dbr:NL_(complexity) dbr:NP_(complexity) dbr:Ulrike_Sattler dbr:Julia_Robinson dbr:Boolean_circuit dbr:Computable_number dbr:Intuitionistic_type_theory dbr:Polynomial_hierarchy dbr:Ambiguity dbr:NP-hardness dbr:St-connectivity dbr:Dominating_set dbr:TFNP dbr:Component_(graph_theory) dbr:Set_splitting_problem dbr:Bipartite_realization_problem dbr:Digraph_realization_problem dbr:Graph_realization_problem dbr:NEXPTIME dbr:Ordinal_priority_approach dbr:Regular_language dbr:L_(complexity) dbr:Set_cover_problem dbr:Subgraph_isomorphism_problem dbr:Graph_homomorphism dbr:Arthur–Merlin_protocol dbr:Simon's_problem dbr:Unary_numeral_system dbr:Probabilistically_checkable_proof dbr:Decidability dbr:Structural_rule dbr:Existential_theory_of_the_reals dbr:Expressive_power_(computer_science) dbr:FL_(complexity) dbr:Cook–Levin_theorem dbr:First-order_logic dbr:NP-completeness dbr:Petri_net dbr:Fallibilism dbr:NP-easy dbr:Unrestricted_grammar dbr:R_(complexity) dbr:TC_(complexity) dbr:ESPACE dbr:Complement_(complexity) dbr:Parity_P dbr:Penrose_tiling dbr:Randomized_algorithm dbr:Kripke_semantics dbr:Post_correspondence_problem dbr:Dieter_Rödding dbr:Guillotine_cutting dbr:Constraint_satisfaction_problem dbr:Computational_problem dbr:Omega_language dbr:Viable_system_model dbr:Wang_tile dbr:Travelling_salesman_problem dbr:P_(complexity) dbr:Hamiltonian_path_problem dbr:Time_complexity dbr:System_F dbr:Ambiguous_grammar dbr:LOGCFL dbr:Immerman–Szelepcsényi_theorem dbr:3-dimensional_matching dbr:Finitely_generated_group dbr:Las_Vegas_algorithm dbr:Richardson's_theorem dbr:EXPTIME dbr:E_(complexity) dbr:Emptiness_problem dbr:♯P dbr:Chromatic_polynomial dbr:Clique_problem dbr:Reduction_(complexity) dbr:Turing_degree dbr:Bipartite_dimension dbr:Structural_complexity_theory dbr:Context-sensitive_grammar dbr:Function_problem dbr:P-complete dbr:PSPACE-complete dbr:RE_(complexity) dbr:UP_(complexity) dbr:Satisfiability_modulo_theories dbr:Decider_(Turing_machine) dbr:Monadic_predicate_calculus dbr:Graph_toughness dbr:Weighted_automaton dbr:PP_(complexity) dbr:Co-NP-complete dbr:EXPSPACE dbr:NC_(complexity) dbr:Oracle_machine dbr:PCP_theorem dbr:Business_decision_mapping dbr:Time_hierarchy_theorem dbr:List_of_computability_and_complexity_topics dbr:List_of_mathematical_logic_topics dbr:Proof_of_impossibility dbr:List_of_NP-complete_problems dbr:Computer_bridge dbr:Tag_system dbr:Many-one_reduction dbr:Undecidable_problem dbr:Outline_of_logic dbr:PolyL dbr:Induced_subgraph_isomorphism_problem dbr:List_of_PSPACE-complete_problems dbr:Uninterpreted_function dbr:Quantum_supremacy dbr:Bottleneck_traveling_salesman_problem dbr:Computation_tree dbr:Conjugacy_problem dbr:NE_(complexity) dbr:NL-complete dbr:Nonelementary_problem dbr:Betweenness dbr:P/poly dbr:Padding_argument dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Decidable_problem dbr:Enumeration_algorithm dbr:Turing_jump dbr:Space_hierarchy_theorem dbr:Quadratic_knapsack_problem dbr:Generic-case_complexity dbr:Maximum_common_induced_subgraph dbr:Skolem_arithmetic dbr:Resource_bounded_measure dbr:MAX-3SAT dbr:Maximum_satisfiability_problem dbr:Galactic_algorithm dbr:Size-change_termination_principle dbr:Advice_(complexity) dbr:MAXEkSAT dbr:Polynomial-time_counting_reduction dbr:Intersection_non-emptiness_problem dbr:Multiway_number_partitioning dbr:Solvable_problem dbr:Type_inhabitation dbr:2-EXPTIME dbr:Glossary_of_artificial_intelligence dbr:AWPP_(complexity) dbr:Decidability_problems dbr:Decision_problems dbr:Decision_procedure dbr:Decision_variant dbr:Decision_version
is foaf:primaryTopic of	wikipedia-en:Word_problem_(computability) wikipedia-en:Decision_problem