Revision #86 → #1105 · back to history
addedComputational complexity theory32ccbdb06cea
addedComputational problem1b89e5c51015
addedInherently difficult problem28b8d337d4fb
addedProblem instancebf68977df9a3
addedPrimality testing instance9354d69ce6bc
addedTravelling salesman instance7c4ac1fa495c
addedInstance as string over an alphabet77f65e368822
addedDecision problemf73b86acb908
addedGraph connectivity decision problem46a880d7fb56
addedFunction problem42eacc285d4c
addedMultiplication recast as decision problem77078817ea6c
addedWorst-case time complexity253578e2296a
addedPolynomial time algorithmc846ac825e66
addedCobham's thesisd410c8d995b8
addedTuring machineec0d005c91df
addedChurch–Turing thesisb379880e5c29
addedDeterministic Turing machine7f41c4d74fcc
addedProbabilistic Turing machine84fbf4e60218
addedNon-deterministic Turing machineab832f88c98d
addedEquivalence of deterministic machine models279ea0750e4e
addedTime required by a Turing machine6571885d332c
addedDTIME complexity class91e3d1c822c4
addedBest, worst and average case complexity729891e35252
addedQuicksort complexity75067fcec4d5
addedComplexity class6b546b0c2827
addedCobham–Edmonds thesis1d7fa6737c84
addedComplexity class Pd14aa02b376d
addedSavitch's theorem (PSPACE = NPSPACE)03c074267299
addedTime hierarchy theorem10ccda65277c
addedSpace hierarchy theoremc988088d864d
addedP strictly contained in EXPTIMEdb330eca6bcf
addedReductione7bb7a21f897
addedSquaring reduces to multiplication774c2b915bc8
addedHard for a complexity classe0ac9d08bf94
addedComplete for a complexity class888e7d639b96
addedP is contained in NP8d57f1c402e9
addedLadner's theorem (NP-intermediate problems)71b044bbc8b6
addedGraph isomorphism problem03e8c9553a2c
addedInteger factorization problem91107ee26cda
addedco-NP (complement class)60dda574738c
addedIntractable problema91906efcd0b
addedTractable problem2c4dc576c5d1
addedEXPTIME-hard problems are intractable33aef0290ccf
addedPresburger arithmetic not in Pe3557cb85f99
addedExponential-time program runtimefc77b53297c5