P和NP问题是千年问题，一般书上只有几页说这，学了ZF公理集合论可能不够，要学当代的NBG集合论(N就是冯。诺曼依）

真正的问题看下面的众多符号
http://qwiki.stanford.edu/index.php/Complexity_Zoo

Symbols
0-1-NPC - 1NAuxPDAp - 2-EXP - 3SUM-hard - #AC0 - #L - #L/poly - #GA - #P - #W[t] - ⊕EXP - ⊕L - ⊕L/poly - ⊕P - ⊕SAC0 - ⊕SAC1

A
A0PP - AC - AC0 - AC0[m] - AC1 - ACC0 - AH - AL - ALL - ALOGTIME - AlgP/poly - Almost-NP - Almost-P - Almost-PSPACE - AM - AMEXP - AM ∩ coAM - AM[polylog] - AmpMP - AmpP-BQP - AP - APP - APX - ATIME - AUC-SPACE(f(n)) - AuxPDA - AVBPP - AvgE - AvgP - AW

- AWPP - AW[SAT] - AW

- AW[t] - AxP - AxPP

B
βP - BH - BPd(P) - BPE - BPEE - BPHSPACE(f(n)) - BPL - BP•NP - BPP - BPPcc - BPPkcc - BPPKT - BPP/log - BPP/mlog - BPP//log - BPP/rlog - BPP-OBDD - BPPpath - BPQP - BPSPACE(f(n)) - BPTIME(f(n)) - BQNC - BQNP - BQP - BQP/log - BQP/poly - BQP/mlog - BQP/mpoly - BQP/qlog - BQP/qpoly - BQP-OBDD - BQPSPACE - BQPCTC - BQPtt/poly - BQTIME(f(n)) - k-BWBP

C
C=AC0 - C=L - C=P - CC - CC0 - CFL - CLOG - CH - Check - CL#P - CkP - CNP - coAM - coC=P - cofrIP - Coh - coMA - coModkP - compIP - compNP - coNE - coNEXP - coNL - coNP - coNPcc - coNP/poly - coNQP - coRE - coRNC - coRP - coSL - coSPARSE - coUCC - coUP - CP - CSIZE(f(n)) - CSL - CSP - CZK

D
D#P - DCFL - Δ2P - δ-BPP - δ-RP - DET - DiffAC0 - DisNP - DistNP - DP - DQP - DSPACE(f(n)) - DTIME(f(n)) - DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC0

E
E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - ELkP - EP - EPTAS - k-EQBP - EQP - EQPK - EQTIME(f(n)) - ESPACE - ∃BPP - ∃NISZK - EXP - EXP/poly - EXPSPACE

F
FBQP - Few - FewEXP - FewP - FH - FIXP - FNL - FNL/poly - FNP - FO - FO(DTC) - FO(LFP) - FO(PFP) - FO(TC) - FO(t(n)) - FOLL - FP - FPNP[log] - FPR - FPRAS - FPT - FPTnu - FPTsu - FPTAS - FQMA - frIP - F-TAPE(f(n)) - F-TIME(f(n))

G
GA - GAN-SPACE(f(n)) - GapAC0 - GapL - GapP - GC(s(n),C) - GCSL - GI - GLO - GPCD(r(n),q(n)) - G[t]

H
HalfP - HeurBPP - HeurBPTIME(f(n)) - HeurDTIMEδ(f(n)) - HeurP - HeurPP - HeurNTIMEδ(f(n)) - HkP - HVSZK

I
IC[log,poly] - IP - IPP - IP[polylog]

L
L - LC0 - LH - LIN - LkP - LOGCFL - LogFew - LogFewNL - LOGLOG - LOGNP - LOGSNP - L/poly - LWPP

M
MA - MA' - MAC0 - MAE - MAEXP - mAL - MAPOLYLOG - MaxNP - MaxPB - MaxSNP - MaxSNP0 - mcoNL - MinPB - MIP - MIP*[2,1] - MIPEXP - (Mk)P - mL - MM - MMSNP - mNC1 - mNL - mNP - ModkL - ModL - ModkP - ModP - ModZkL - mP - MP - MPC - mP/poly - mTC0

N
NAuxPDAp - NC - NC0 - NC1 - NC2 - NE - NE/poly - Nearly-P - NEE - NEEE - NEEXP - NEXP - NEXP/poly - NIPZK - NIQSZK - NISZK - NISZKh - NL - NL/poly - NLIN - NLOG - NONE - NP - NPC - NPC - NPcc - NPkcc - NPI - NP ∩ coNP - (NP ∩ coNP)/poly - NP/log - NPMV - NPMV-sel - NPMVt - NPMVt-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NPR - NPSPACE - NPSV - NPSV-sel - NPSVt - NPSVt-sel - NQP - NSPACE(f(n)) - NT - NT* - NTIME(f(n))

O
OCQ - OptP

P
P - P/log - P/poly - P#P - P#P[1] - PCTC - PAC0 - PBP - k-PBP - PC - Pcc - Pkcc - PCD(r(n),q(n)) - P-Close - PCP(r(n),q(n)) - PermUP - PEXP - PF - PFCHK(t(n)) - PH - PHcc - Φ2P - PhP - Π2P - PINC - PIO - PK - PKC - PL - PL1 - PL∞ - PLF - PLL - PLS - PNP - P||NP - PNP[k] - PNP[log] - PNP[log^2] - P-OBDD - PODN - polyL - PostBQP - PP - PPcc - PP/poly - PPA - PPAD - PPADS - PPP - PPP - PPSPACE - PQUERY - PR - PR - PrHSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PromiseUP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PSPACE/poly - PT1 - PTAPE - PTAS - PT/WK(f(n),g(n)) - PZK

Q
Q - QAC0 - QAC0[m] - QACC0 - QACf0 - QAM - QCFL - QCMA - QH - QIP - QIP[2] - QMA - QMA-plus - QMA(2) - QMA1 - QMAlog - QMAM - QMA/qpoly - QMIP - QMIPle - QMIPne - QNC - QNC0 - QNCf0 - QNC1 - QP - QPLIN - QPSPACE - QRG - QS2P - QSZK

R
R - RBQP - RE - REG - RevSPACE(f(n)) - RG - RG[1] - RHL - RHSPACE(f(n)) - RL - RNC - RP - RPkcc - RPP - RQP - RSPACE(f(n))

S
S2P - S2-EXP•PNP - SAC - SAC0 - SAC1 - SAPTIME - SBP - SBQP - SC - SE - SEH - SelfNP - SFk - Σ2P - SKC - SL - SLICEWISE PSPACE - SNP - SO - SO(Horn) - SO(Krom) - SO(LFP) - SO(TC) - SO[t(n)] - SP - span-P - SPARSE - SPL - SPP - SQG - SUBEXP - symP - SZK - SZKh

T
TALLY - TC0 - TFNP - Θ2P - TreeBQP - TREE-REGULAR

U
UAP - UCC - UCFL - UE - UL - UL/poly - UP - UPPcc - US

V
VCk - VCOR - VNCk - VNPk - VPk - VPL - VQPk

W
W[1] - WAPP - WHILE - W

- WPP - W[SAT] - W

- W[t] - W*[t]

X
XOR-MIP*[2,1] - XP - XPuniform

Y
YACC - YP - YPP - YQP

Z
ZBQP - ZPE - ZPP - ZPTIME(f(n)) - ZQP

Retrieved from "http://qwiki.stanford.edu/index.php/Complexity_Zoo"

算法复杂性是算法运行所需要的计算机资源的量， 　　需要时间资源的量称为时间复杂性，需要的空间资源的 　　量称为空间复杂性。这个量应该只依赖于算法要解的问 　　题的规模、算法的输入和算法本身的函数。如果分别用 　　N、I和A表示算法要解问题的规模、算法的输入和算法 　　本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。 　　一般把时间复杂性和空间复杂性分开，并分别用T和S来 　　表示，则有： T=T(N,I)和S=S(N,I) 。

[课程]Android-CTF解题方法汇总！