{
localUrl: '../page/decision_problem.html',
arbitalUrl: 'https://arbital.com/p/decision_problem',
rawJsonUrl: '../raw/4kz.json',
likeableId: '2796',
likeableType: 'page',
myLikeValue: '0',
likeCount: '4',
dislikeCount: '0',
likeScore: '4',
individualLikes: [
'EricBruylant',
'VladArber',
'GregorGerasev',
'StephanieZolayvar'
],
pageId: 'decision_problem',
edit: '8',
editSummary: 'Added summary.',
prevEdit: '7',
currentEdit: '8',
wasPublished: 'true',
type: 'wiki',
title: 'Decision problem',
clickbait: 'Formalization of general problems',
textLength: '2991',
alias: 'decision_problem',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'EricBruylant',
editCreatedAt: '2016-07-04 18:24:40',
pageCreatorId: 'JaimeSevillaMolina',
pageCreatedAt: '2016-06-18 14:04:27',
seeDomainId: '0',
editDomainId: 'AlexeiAndreev',
submitToDomainId: '0',
isAutosave: 'false',
isSnapshot: 'false',
isLiveEdit: 'true',
isMinorEdit: 'false',
indirectTeacher: 'false',
todoCount: '2',
isEditorComment: 'false',
isApprovedComment: 'true',
isResolved: 'false',
snapshotText: '',
anchorContext: '',
anchorText: '',
anchorOffset: '0',
mergedInto: '',
isDeleted: 'false',
viewCount: '143',
text: '[summary: A decision problem is a question of the form "does [-bitstring] $w$ have [-property] $p$, yes or no?"]\n\nA **decision problem** is a subset $D$ of a set of instances $A$, where generally $A$ is the set of finite [-bitstrings] $\\{0,1\\}^*$.\n\nIn plain English, a decision problem is composed by a number of members of a collection, which generally share a common property. \n\nIn plainer English, a decision problem is a question of the form "does bitstring $w$ have property $p$, yes or no?" \n\nEvery question that fits the set form (is this string in the set?) can be re-expressed as "does this bitstring have the property of being in the set?" Everything that fits the property form can be re-expressed in set form as well, because a property implicitly specifies a set of things that have the property. Thus, the two forms are equivalent.\n\nIt is called a decision problem because we are trying to *decide* whether a given bitstring belongs to the set or not.\n\nA **solution** of the problem would consist in a procedure which given an instance $w$ of $A$ decides correctly in finite time whether $w$ belongs to $D$ or not. That is, a solution consists in a way of identifying the common trait shared by the members of $D$ which distinguish them from the rest of instances in $A$.\n\nWe say that a problem is [-decidable] if there exists a solution which works for every instance. Trivially, finite decision problems are decidable, since we can have a look-up list with every element which we would consult every time we are given an instance to classify. If the instance corresponds to an element in the list, we accept it, and otherwise reject it. \n\nWe say that a decision problem is [-semidecidable] if there is a procedure which, in finite time, identifies members of $D$, but fails to [-halt] and reject instances which do not belong to $D$.\n\nDecision problems can be classified according to their difficulty of solving in [ complexity classes], and are a central object of study in [-49w].\n\n#Examples\n##Graph connectedness\nSuppose we encode every possible finite graph, up to isomorphism, in the collection of finite bitstrings. Then we could define:\n$$\nCONNECTED = \\{s\\in\\{0,1\\}^*:\\text{$s$ represents a connected graph}\\}\n$$\nWhich would be a [graph_connectedness decidable decision problem].\n\n##Tautology identification\nLet $TAUTOLOGY$ be the collection of formulas of [-first_order_logic] which are true for every [mathematical_interpretation interpretation]. Then [ $TAUTOLOGY$ is a semidecidable decision problem], as if a formula is [-valid] we can search for a proof, but otherwise, we do not have an effective procedure to decide that a formula is not valid.\n\n##Primality\nLet:\n$$\nPRIMES = \\{ x\\in \\mathbb{N}:\\text{$x$ is prime}\\}\n$$\nThen $PRIMES$ is a decidable decision problem.\n\nWe can alternately define\n$$\nPRIMES = \\{s\\in\\{0,1\\}^*:\\text{$s$ represent a prime number in base $2$}\\}\n$$\nThis illustrates that we can specify a particular decision problem in different ways.',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '1',
maintainerCount: '1',
userSubscriberCount: '0',
lastVisit: '',
hasDraft: 'false',
votes: [],
voteSummary: 'null',
muVoteSummary: '0',
voteScaling: '0',
currentUserVote: '-2',
voteCount: '0',
lockedVoteType: '',
maxEditEver: '0',
redLinkCount: '0',
lockedBy: '',
lockedUntil: '',
nextPageId: '',
prevPageId: '',
usedAsMastery: 'false',
proposalEditNum: '0',
permissions: {
edit: {
has: 'false',
reason: 'You don't have domain permission to edit this page'
},
proposeEdit: {
has: 'true',
reason: ''
},
delete: {
has: 'false',
reason: 'You don't have domain permission to delete this page'
},
comment: {
has: 'false',
reason: 'You can't comment in this domain because you are not a member'
},
proposeComment: {
has: 'true',
reason: ''
}
},
summaries: {},
creatorIds: [
'JaimeSevillaMolina',
'EricBruylant',
'AlexAppel'
],
childIds: [],
parentIds: [
'complexity_theory'
],
commentIds: [
'4lk'
],
questionIds: [],
tagIds: [
'start_meta_tag'
],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [],
subjects: [],
lenses: [],
lensParentId: '',
pathPages: [],
learnMoreTaughtMap: {},
learnMoreCoveredMap: {},
learnMoreRequiredMap: {},
editHistory: {},
domainSubmissions: {},
answers: [],
answerCount: '0',
commentCount: '0',
newCommentCount: '0',
linkedMarkCount: '0',
changeLogs: [
{
likeableId: '2928',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '15278',
pageId: 'decision_problem',
userId: 'EricBruylant',
edit: '8',
type: 'newEdit',
createdAt: '2016-07-04 18:24:40',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: 'Added summary.'
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '15277',
pageId: 'decision_problem',
userId: 'EricBruylant',
edit: '0',
type: 'newTag',
createdAt: '2016-07-04 18:24:28',
auxPageId: 'start_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '15276',
pageId: 'decision_problem',
userId: 'EricBruylant',
edit: '0',
type: 'deleteTag',
createdAt: '2016-07-04 18:23:53',
auxPageId: 'needs_summary_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '2929',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '15197',
pageId: 'decision_problem',
userId: 'AlexAppel',
edit: '7',
type: 'newEdit',
createdAt: '2016-07-03 17:02:27',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '14445',
pageId: 'decision_problem',
userId: 'EricBruylant',
edit: '6',
type: 'newEdit',
createdAt: '2016-06-23 02:06:23',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '14288',
pageId: 'decision_problem',
userId: 'JaimeSevillaMolina',
edit: '5',
type: 'newEdit',
createdAt: '2016-06-21 21:13:16',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '2791',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '14133',
pageId: 'decision_problem',
userId: 'EricBruylant',
edit: '4',
type: 'newEdit',
createdAt: '2016-06-20 20:53:04',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13976',
pageId: 'decision_problem',
userId: 'EricRogstad',
edit: '0',
type: 'newTag',
createdAt: '2016-06-19 01:27:19',
auxPageId: 'needs_summary_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13902',
pageId: 'decision_problem',
userId: 'JaimeSevillaMolina',
edit: '3',
type: 'newEdit',
createdAt: '2016-06-18 14:25:31',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13901',
pageId: 'decision_problem',
userId: 'JaimeSevillaMolina',
edit: '2',
type: 'newEdit',
createdAt: '2016-06-18 14:25:13',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13897',
pageId: 'decision_problem',
userId: 'JaimeSevillaMolina',
edit: '0',
type: 'newParent',
createdAt: '2016-06-18 14:04:44',
auxPageId: 'complexity_theory',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13895',
pageId: 'decision_problem',
userId: 'JaimeSevillaMolina',
edit: '1',
type: 'newEdit',
createdAt: '2016-06-18 14:04:27',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}