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

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

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n9http://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Computational_problem
rdf:type
dbo:Planet
rdfs:label
Computational problem
rdfs:comment
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n.
owl:sameAs
yago-res:Computational_problem freebase:m.0cbp56
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Main dbt:Efn dbt:Citation dbt:No_footnotes dbt:Notelist
dct:subject
dbc:Computational_problems dbc:Theoretical_computer_science
gold:hypernym
dbr:Object
prov:wasDerivedFrom
n9:Computational_problem?oldid=1071122850&ns=0
dbo:wikiPageID
4594672
dbo:wikiPageLength
7201
dbo:wikiPageRevisionID
1071122850
dbo:wikiPageWikiLink
dbr:Undecidable_problem dbr:Function_problem dbr:Decision_problem dbr:P_(complexity) dbc:Theoretical_computer_science dbr:Partial_function dbr:Analysis_of_algorithms dbr:NP-hardness dbr:Property_testing dbr:Cambridge_University_Press dbr:Regular_expression dbr:Primality_test dbr:Integer_factorization dbr:Abstract_machine dbr:Theoretical_computer_science dbr:Computational_complexity_theory dbc:Computational_problems dbr:Counting_problem_(complexity) dbr:Computational_complexity dbr:Complexity_class dbr:Algorithm dbr:Set_(mathematics) dbr:Operations_research dbr:Lateral_computing dbr:Optimization_problem dbr:Interactive_proof_system dbr:Hardness_of_approximation dbr:Independent_set_(graph_theory) dbr:Transcomputational_problem dbr:Search_problem dbr:Relation_(mathematics) dbr:Combinatorial_optimization dbr:BQP dbr:Model_of_computation dbr:Travelling_salesman_problem dbr:Promise_problem dbr:String_(computer_science) dbr:The_Princeton_Companion_to_Mathematics
dbo:abstract
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n. Computational problems are one of the main objects of study in theoretical computer science. The field of computational complexity theory attempts to determine the amount of resources (computational complexity) solving a given problem will require and explain why some problems are intractable or undecidable. Computational problems belong to complexity classes that define broadly the resources (e.g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with various abstract machines. For example, the complexity class P for cassical machines, and BQP for quantum machines. It is typical of many problems to represent both instances and solutions by binary strings, namely elements of {0, 1}*. For example, numbers can be represented as binary strings using binary encoding.
foaf:isPrimaryTopicOf
n9:Computational_problem