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