കമ്പ്യൂട്ടർ അൽഗോരിതങ്ങൾക്ക് പ്രധാനമായും രണ്ടു തരത്തിലുള്ള സമയ സങ്കീർണ്ണതയാണുള്ളത്. ഒന്ന് താരതമ്യേന കാര്യക്ഷമത കൂടിയ ബഹുപദ സമയ സങ്കീർണതയാണ് (polynomial time complexity). (ഉദാ : തിരയൽ, ക്രമീകരണം തുടങ്ങിയവ). ഇത്തരം പ്രശ്നങ്ങളെ പി ടൈപ്പ് പ്രശ്നങ്ങൾ എന്ന് വിളിയ്ക്കുന്നു.

അടുത്തത് വളരെ കാര്യക്ഷമത കുറഞ്ഞ എക്സ്പോണെൻഷ്യൽ സമയ സങ്കീർണ്ണതയുള്ള പ്രശ്നങ്ങൾ ആണ്. ഉദാ : ട്രാവലിങ് സേൽസ്‌മാൻ അൽഗോരിതം, നാപ്സാക്ക് പ്രോബ്ലം. രണ്ടാമത്തെ പ്രശ്നം ഇങ്ങനെ വിവരിയ്ക്കാം, 1,2,3 ...20 കിലോ വരെ ഭാരമുള്ള ഒരു കൂട്ടം കല്ലുകൾ തന്നിട്ടുണ്ടെങ്കിൽ അവയിൽ നിന്നും കൃത്യം 50 കിലോ തൂക്കം എങ്ങനെ ഉണ്ടാക്കിയെടുക്കാം? ഇത്തരം പ്രശ്നങ്ങൾക്കുള്ള സാമാന്യ അൽഗോരിതം ഓരോരോ കോമ്പിനേഷൻ ഉണ്ടാക്കി തന്നിരിയ്ക്കുന്ന ചോദ്യത്തെ അത് പരിഹരിക്കുന്നുണ്ടോ എന്ന് നോക്കലാണ്. കല്ലിന്റെ ഉദാഹരണത്തിൽ ആദ്യം ഒരു കൂട്ടം കല്ലുകൾ എടുക്കുക, തൂക്കി നോക്കുക, 50 കിലോ ആണെങ്കിൽ ഉത്തരം കിട്ടി, ഇല്ലെങ്കിൽ വേറെ ഒരു കൂട്ടം എടുക്കുക, അങ്ങനെ ഉത്തരം കിട്ടുന്നതുവരെ തുടരുക. 

ഒരു കൂട്ടം കല്ലുകൾ കിട്ടിയാൽ അത് 50 കിലോ തൂക്കമുള്ളതാണോ അല്ലയോ എന്ന് നോക്കുന്നത് വളരെ എളുപ്പത്തിൽ ചെയ്യാൻ കഴിയും.(ബഹുപദ സമയ സങ്കീർണ്ണതയോടെ). വിവിധ കോമ്പിനേഷനുകൾ ഒന്നിന് പുറകെ ഒന്നായി ഉണ്ടാക്കി എടുക്കുന്നതാണ് ഇവിടുത്തെ ശ്രമകരമായ പ്രശ്‌നം. നമുക്ക് കണക്കാക്കേണ്ട കോമ്പിനേഷനുകളുടെ എണ്ണം വളരെ പെട്ടെന്ന് വളരെ കൂടും. വിവിധ കോമ്പിനേഷനുകൾ ഒന്നിന് പുറകെ ഒന്നായി ഉണ്ടാക്കി എടുക്കുന്നതാണ് ഇവിടുത്തെ ശ്രമകരമായ പ്രശ്‌നം ഉദാ : 2 കല്ലുകളെ ഉള്ളുവെങ്കിൽ അതിനെ നാല് തരത്തിൽ ഗ്രൂപ്പ് ചെയ്യാമല്ലോ. ശരിയായ ഉത്തരം കിട്ടണമെങ്കിൽ നമ്മൾ ഏറ്റവും മോശം അവസ്ഥയിൽ നാലു കോമ്പിനേഷനുകളും തൂക്കി നോക്കണം. അതുപോലെ 3 കല്ലുകൾ ഉണ്ടെങ്കിൽ 8 തരത്തിലും 10 കല്ലുകൾ ഉണ്ടെങ്കിൽ 1024 തരത്തിലും ഗ്രൂപ്പ് ചെയ്യാം. എന്നാൽ 32 കല്ലുകൾ ഉണ്ടെങ്കിൽ ഇതിന്റെ എണ്ണം 4294967296 ആയി കൂടുന്നു. അതായത് ശരിയായ ഉത്തരം കിട്ടണമെങ്കിൽ നമ്മൾ ചിലപ്പോൾ ഈ ഗ്രൂപ്പിലെ അവസാനത്തെ കോമ്പിനേഷൻ തൂക്കി നോക്കുമ്പോൾ ആയിരിയ്ക്കും. 50 കല്ലുകൾ ആണെങ്കിൽ 1125899906842624 ആകും. ഒരു കൂട്ടം ഉണ്ടാക്കി തൂക്കി നോക്കാൻ 10 സെക്കന്റ് എടുക്കുന്നുവെങ്കിൽ ഒരാൾക്ക് ഇങ്ങനെ ചെയ്തു നോക്കാൻ 357020518 വർഷങ്ങൾ വേണ്ടി വരും. ഇത്തരം പ്രശ്നങ്ങൾ എൻ.പി ടൈപ്പ് പ്രശ്നങ്ങൾ എന്ന പേരിലാണ് അറിയപ്പെടുന്നത്.

"എൻ.പി പ്രശ്നങ്ങൾക്ക് ബഹുപദ സങ്കീർണതയോടെ ഉത്തരം കണ്ടുപിടിയ്ക്കാനാകുമോ" എന്ന ചോദ്യമാണ് പി വേഴ്സസ് എൻ പി പ്രശ്നം. അതായത് പി പ്രശ്നങ്ങളുടെ ഗണവും എൻ.പി പ്രശ്നങ്ങളുടെ ഗണവും ഒന്നാണോ എന്നുള്ള ചോദ്യം (P = NP ?). കമ്പ്യൂട്ടർ / ഗണിത ശാസ്ത്ര വിഭാഗങ്ങളിലെ ഏറ്റവും പ്രധാനപ്പെട്ട പരിഹരിയ്ക്കപ്പെടാത്ത പ്രശ്നങ്ങളിൽ ഒന്നാണിത്.

കൂടുതൽ ഗണിത ശാസ്ത്രജ്ഞരും P ≠ NP എന്നാണ് വിശ്വസിയ്ക്കുന്നത്. എന്നാൽ ഇത് ഇതുവരെ തെളിയിയ്ക്കപ്പെട്ടിട്ടില്ല.

റീമാൻ പരികല്പന (Riemann hypothesis)
പി വേഴ്സസ് എൻ പി പ്രശ്നം (P versus NP)
നേവിയർ-സ്റ്റോക്സ് എക്സിസ്റ്റൻസ് ആൻഡ് സ്മൂത്ത്നെസ് (Navier–Stokes existence and smoothness)
ഹോഡ്ജ് കൺജെക്ചർ (Hodge conjecture)