Revision #240 → #1452 · back to history
addedClass P (informal)ce2903fe88e2
addedClass NP (informal)ee8d8faae0ca
addedGeneralized Sudoku7487cb0c09be
addedClass NPcfd9d9aa7cfd
addedP is contained in NP0655d6484cbd
addedThe P versus NP question6527a417bb2b
addedNP-complete3330788733c7
addedCook–Levin theorem (SAT is NP-complete)0c842586681f
addedNP-complete problem in P implies P = NPb2bebbaa99aa
addedTrivial NP-complete problemc839dc059aa5
addedNP-completeness by reduction7a3a599ad65e
addedEXPTIME-completea221c5c5afba
addedP ≠ EXPTIMEb8879c7489dc
addedChess on N×N board is EXPTIME-complete63702a43d179
addedFischer–Rabin (Presburger arithmetic lower bound)1559d7264f82
addedUndecidable problems343b4a6a6e00
addedClass #Pe7713660d713
added#P-complete58e72aae7079
addedLadner's theorem17c12a9c1372
addedNP-intermediatef827a7e39d3a
addedGraph isomorphism problem9c0909568e3d
addedGI NP-complete collapses PH to second level33e4b9f250fe
addedBabai's quasi-polynomial GI algorithmc2ebe2ee25ae
addedInteger factorization problem0cab7a4ec51d
addedFactorization NP-complete collapses PH to first leveldc0f50943acf
addedGeneral number field sieve1cf97e7a65ed
addedShor's algorithm7da12763881d
addedCobham's thesisaac9c26ff8c0
addedGraph minor testing in O(n^2)cd272f14e1b0
addedSimplex algorithm1063b1e8be2f
addedP = NP implies NP = co-NP and P = PHc1d9f0c38b32
addedDLIN and NLIN76e0499e93c6
addedDLIN ≠ NLIN7d97072d0371
addedP characterized by FO + least fixed point1431d00c546f
addedFagin's theorem (NP = existential SO logic)513bbd8b5331
addedP = NP iff P = PH125ea6671535
addedLevin's SUBSET-SUM algorithm9cf4f7879742
addedDecision problem99592cf972e0
addedClass P (formal)8ee79c5f291d
addedDeterministic polynomial-time Turing machineaa156b5ea6fc
addedClass NP (verifier)e251cab11980
addedNP via certificate relation30d6d9f5f652
addedVerifier and certificatedd451bfd6dab
addedCOMPOSITE ∈ NPf98f2b9118e5
addedCOMPOSITE ∈ P (AKS primality test)680ff74569c7
addedNP-complete (formal)50fd40360574
addedNP-completeness via reduction from NP-complete3d828e2109df
addedVP vs VNP problem359344d0a4a1
addedFPT vs W[1]273f9f09228f