Re:One-sentence proof of Fermat's theorem on sums of two squ...
by Ar-Curunir on Tuesday July 26, 2016 @07:14PM
(#12169428)
> We really don't have a good terminology for distinguishing between efficient constructive proofs (those corresponding to efficient algorithms) and inefficient ones...
We do: the complexity classes P and NP. Ok, technically this is a polynomial time decidable language (does there exist etc. etc.), so perhaps consider FP and FNP (the function variants of P & NP).
We do: the complexity classes P and NP. Ok, technically this is a polynomial time decidable language (does there exist etc. etc.), so perhaps consider FP and FNP (the function variants of P & NP).