Statements (23)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:field |
theoretical computer science
|
| gptkbp:generalizes |
gptkb:generalized_Post_correspondence_problem
|
| gptkbp:hasReductionFrom |
halting problem
|
| gptkbp:hasSolutionIf |
there exists a sequence of dominoes such that the concatenation of the top strings equals the concatenation of the bottom strings
|
| gptkbp:hasVariant |
gptkb:bounded_Post_correspondence_problem
|
| https://www.w3.org/2000/01/rdf-schema#label |
Post correspondence problem
|
| gptkbp:input |
finite set of dominoes
|
| gptkbp:introduced |
gptkb:Emil_Post
|
| gptkbp:introducedIn |
1946
|
| gptkbp:isNPComplete |
false
|
| gptkbp:isRecursivelyEnumerable |
true
|
| gptkbp:isTuringComplete |
true
|
| gptkbp:isUndecidable |
true
|
| gptkbp:output |
yes/no
|
| gptkbp:reduces |
undecidable problems
|
| gptkbp:relatedTo |
computability theory
formal languages halting problem |
| gptkbp:type |
word problem
|
| gptkbp:usedIn |
proving undecidability
|
| gptkbp:bfsParent |
gptkb:Emil_Post
|
| gptkbp:bfsLayer |
5
|