U teoriji računske složenosti, postoje tri uobičajene metode dokaza koje se široko koriste za analizu efikasnosti i težine algoritama. Ove metode pružaju rigorozne matematičke tehnike za utvrđivanje složenosti računskih problema. Oni su poznati kao metoda dijagonalizacije, metoda redukcije i probabilistička metoda. Svaka od ovih metoda nudi