{
localUrl: '../page/complexity_theory.html',
arbitalUrl: 'https://arbital.com/p/complexity_theory',
rawJsonUrl: '../raw/49w.json',
likeableId: '2684',
likeableType: 'page',
myLikeValue: '0',
likeCount: '4',
dislikeCount: '0',
likeScore: '4',
individualLikes: [
'EricBruylant',
'MeaganSullivan',
'JaimeSevillaMolina',
'AdomHartell'
],
pageId: 'complexity_theory',
edit: '19',
editSummary: '',
prevEdit: '17',
currentEdit: '19',
wasPublished: 'true',
type: 'wiki',
title: 'Complexity theory',
clickbait: 'Study of the computational resources needed to compute something',
textLength: '4191',
alias: 'complexity_theory',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'AdomHartell',
editCreatedAt: '2016-10-08 17:56:04',
pageCreatorId: 'JaimeSevillaMolina',
pageCreatedAt: '2016-06-14 20:38:51',
seeDomainId: '0',
editDomainId: 'AlexeiAndreev',
submitToDomainId: '0',
isAutosave: 'false',
isSnapshot: 'false',
isLiveEdit: 'true',
isMinorEdit: 'false',
indirectTeacher: 'false',
todoCount: '12',
isEditorComment: 'false',
isApprovedComment: 'true',
isResolved: 'false',
snapshotText: '',
anchorContext: '',
anchorText: '',
anchorOffset: '0',
mergedInto: '',
isDeleted: 'false',
viewCount: '158',
text: '[summary: Study of the computational resources needed to solve a problem, usually time and memory]\n\n**Complexity theory** is the study of the efficiency of algorithms with respect to several metrics, usually time and memory usage. Complexity theorists aim to classify different problems into [complexity_class classes of difficulty] and study the relations that hold between the classes.\n\nWhen studying [ computability], we are concerned with the identification of that which is or not computable in an ideal sense, without worrying about time or memory limitations.\n\nHowever, often in practice we have to be more pragmatic. A program which takes a [42m googol] years to run is not going to see much use. If you need more [ GbBytes] to solve a computational problem that atoms exist in the universe, you may as well go ahead and declare the problem unsolvable for all practical purposes.\n\n**Complexity theory** raises the standards of computability in drawing the boundary between that which you can do with a computer and that which you cannot. It concerns the study of the [oh_notation asymptotic behavior] of programs when fed inputs of growing size, in terms of the resources they consume. The kind of resources with which complexity theorists work more often are the *time* a program takes to finish and the highest *memory usage* %%note:the memory usage is frequently called **space complexity**%% in any given point of the execution.\n\nComplexity theory allows us to have a deeper understanding of what makes an algorithm efficient, which in turn allows us to develop better and faster algorithms. Surprisingly enough, it turns out that proving that some computational problems are hard to solve has incredibly important practical applications in [-cryptography].\n\n----\n\nThe abstract framework in which we develop this theory are [ Turing machines] and [ decision problems]. In this context, the [ time complexity] is associated with the number of steps a TM takes to halt and return an output, while the [ space complexity] corresponds to the length of the tape we would need for the TM to never fall off when moving left or right.\n\nOne may worry that the complexity measures are highly dependent on the choice of computational framework used. After all, if we allow our TM to skip two spaces per step each time it moves it is going to take potentially half the time to compute something. However, the asymptotic behavior of complexity is [robustness_of_tm surprisingly robust], though there are [failure_of_strong_CT some caveats].\n\nThe most interesting characterization of complexity comes in the form of [ complexity classes], which break down the family of [ decision problems] into sets of problems which can be solved with particular constraints.\n\nPerhaps the most important complexity class is [ $P$], the class of decision problems which can be efficiently computed %%note:For example, checking whether a graph is connected or not%%. The second best known class is [ $NP$], the class of problems whose solutions can be easily checked %%note:An example is factoring a number: it is hard to factor $221$, but easy to multiply $13$ and $17$ and check that $13 \\cdot 17 = 221$%% . It is an open problem whether those two classes are [4bd one and the same]; that is, that every problem whose solutions are easy to check is also easy to solve.\n\nThere are many more important complexity classes, and it can be daunting to contemplate the sheer variety with which complexity theory deals. Feel free to take a guided tour though the [4b9 complexity zoo] if you want an overview of some of the most relevant.\n\nAn important concept is that of a [ reduction]. Some complexity classes have problems such that if you were able to solve them efficiently you could translate other problems in the class to this one and solve them efficiently. Those are called [ complete problems of a complexity class].\n\n-----\n\nThis page is meant to be a starting point to learn complexity theory from an entry level. If there is any concept which feels mysterious to you, try exploring the greenlinks in their order of appearance. If you feel like the concepts presented are too basic, try a different lens.',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '2',
maintainerCount: '2',
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: 'true',
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',
'EricRogstad',
'AdomHartell'
],
childIds: [
'complexity_zoo',
'P_vs_NP',
'decision_problem',
'polynomial_time_complexity_class'
],
parentIds: [
'math'
],
commentIds: [
'4bq',
'4cc'
],
questionIds: [],
tagIds: [],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [],
subjects: [],
lenses: [
{
id: '41',
pageId: 'complexity_theory',
lensId: 'complexity_zoo',
lensIndex: '0',
lensName: 'Complexity zoo',
lensSubtitle: '',
createdBy: '1',
createdAt: '2016-06-17 21:58:56',
updatedBy: '1',
updatedAt: '2016-06-17 21:58:56'
}
],
lensParentId: '',
pathPages: [],
learnMoreTaughtMap: {},
learnMoreCoveredMap: {},
learnMoreRequiredMap: {},
editHistory: {},
domainSubmissions: {},
answers: [],
answerCount: '0',
commentCount: '0',
newCommentCount: '0',
linkedMarkCount: '0',
changeLogs: [
{
likeableId: '3586',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '2',
dislikeCount: '0',
likeScore: '2',
individualLikes: [],
id: '19951',
pageId: 'complexity_theory',
userId: 'AdomHartell',
edit: '19',
type: 'newEdit',
createdAt: '2016-10-08 17:56:04',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '3589',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '19950',
pageId: 'complexity_theory',
userId: 'AdomHartell',
edit: '18',
type: 'newEdit',
createdAt: '2016-10-08 17:52:10',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '3302',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '18153',
pageId: 'complexity_theory',
userId: 'EricBruylant',
edit: '0',
type: 'newChild',
createdAt: '2016-08-02 17:33:26',
auxPageId: 'polynomial_time_complexity_class',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13896',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '0',
type: 'newChild',
createdAt: '2016-06-18 14:04:44',
auxPageId: 'decision_problem',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '2690',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '13089',
pageId: 'complexity_theory',
userId: 'EricRogstad',
edit: '17',
type: 'newEdit',
createdAt: '2016-06-15 17:46:29',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13026',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '16',
type: 'newEdit',
createdAt: '2016-06-15 11:26:56',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13023',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '15',
type: 'newEdit',
createdAt: '2016-06-15 11:23:51',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '13017',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '14',
type: 'newEdit',
createdAt: '2016-06-15 11:00:30',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '2694',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '12945',
pageId: 'complexity_theory',
userId: 'EricRogstad',
edit: '13',
type: 'newEdit',
createdAt: '2016-06-15 07:51:36',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '2696',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '12943',
pageId: 'complexity_theory',
userId: 'EricRogstad',
edit: '12',
type: 'newEdit',
createdAt: '2016-06-15 07:49:28',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12889',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '11',
type: 'newEdit',
createdAt: '2016-06-14 23:46:13',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12886',
pageId: 'complexity_theory',
userId: 'EricBruylant',
edit: '10',
type: 'newParent',
createdAt: '2016-06-14 23:44:07',
auxPageId: 'math',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12884',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '10',
type: 'newEdit',
createdAt: '2016-06-14 23:37:35',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12883',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '9',
type: 'newEdit',
createdAt: '2016-06-14 23:36:37',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12879',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '8',
type: 'newEdit',
createdAt: '2016-06-14 23:21:04',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12874',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '6',
type: 'newEdit',
createdAt: '2016-06-14 23:05:25',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12806',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '5',
type: 'newChild',
createdAt: '2016-06-14 22:02:56',
auxPageId: 'P_vs_NP',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12802',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '5',
type: 'newChild',
createdAt: '2016-06-14 21:51:47',
auxPageId: 'complexity_zoo',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12794',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '5',
type: 'newEdit',
createdAt: '2016-06-14 20:40:42',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12793',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '4',
type: 'newEdit',
createdAt: '2016-06-14 20:40:24',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12792',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '3',
type: 'newEdit',
createdAt: '2016-06-14 20:39:48',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12791',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '2',
type: 'newEdit',
createdAt: '2016-06-14 20:39:28',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '12790',
pageId: 'complexity_theory',
userId: 'JaimeSevillaMolina',
edit: '1',
type: 'newEdit',
createdAt: '2016-06-14 20:38:51',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'true',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}