函数复杂度类 FP

P 的算法最终回答一个真假位；FP 的算法可能返回整数、路径或翻译后的程序。两者都要求统一的确定性多项式最坏时间，但输出任务不同。说“乘两个整数属于 P”省略了接口；更准确地说，二进制乘积函数属于 FP，而“乘积是否等于给定整数”的判定语言属于 P。

函数值唯一，也不意味着容易计算。一个巨大真值表可以唯一规定某个函数，却未必给出高效算法。反过来，一个允许许多结果的任务，只要固定算法的所有择优规则，就会产生某个单值选择函数；要判断它是否属于 FP，还得证明这台算法的运行界。

把二进制加法写成完整函数接口 ​

输入为可解析的整数对 $⟨a,b⟩$，每个非负整数用无前导零的二进制表示，零单独写作 0。函数输出带 VALUE 标签的 $a+b$；格式不合规则返回 INVALID。给 $a={1011}_2=11$、$b={110}_2=6$，将两者在右侧对齐为 1011 与 0110。

从最低位起，四轮“输入位、进位”分别为 $(1,0,0)$、$(1,1,0)$、$(0,1,1)$、$(1,0,1)$。写出的低到高结果位为 $1,0,0,0$，末尾再写进位 1，正常读序得到 10001，即 17。逐位实现的总工作由输入位数线性控制，反向输出若需临时保存也只增加线性扫描，所以这个函数属于 FP。空输入不是整数零，而是格式错误。

这里整数数值可以很大，位数却只增长一位。位复杂度理路位复杂度Bit complexity · Bit operation complexity固定有限编码与逐位计算模型后，以基本位操作数衡量算法成本，并将中间数的实际位长计入每次算术运算。已经说明完整幂 $2^e$ 的不同情形：输入二进制 $e$，输出要写 $e+1$ 位，可能远长于输入长度的任何多项式。把输出改成文本“2 的 e 次方”会缩短表示，却也改变了函数的输出契约。

复合为什么仍是多项式 ​

若 $f,g\in \mathbf{FP}$，分别由非减多项式 $p,q$ 控制时间，可先完整求出 $y=f(x)$，再计算 $g(y)$。因为 $|y|\le O(p(|x|))$，复合成本至多

其中固定常数 $C$ 吸收输出编码开销，因此 $g\circ f\in \mathbf{FP}$。关键是中间结果的长度已被第一次运行的时间控制；若只知道调用了两个子程序，而不知第一个输出多长，就无法得到此结论。

图关系易判定，不等于函数易求值 ​

给定 $f\in \mathbf{FP}$，它的图关系 $G_f=\{⟨x,y⟩:y=f(x)\}$ 在 P 中：先算 $f(x)$，再与 $y$ 比较即可。但反向只知道 $G_f$ 容易验证，仍是在说“给我候选，我可以检查”，并没有指定怎样找到候选。

即使答案唯一且多项式短，也不能靠遍历所有短串宣称 FP：长度 $m$ 有 $2^m$ 个候选。假定存在难以求逆的长度保持多项式时间置换 $h$，则逆函数值 $h^{-1}(x)$ 唯一，其图关系可检查 $h(y)=x$，却仍按这个假设难以高效求出。这个条件例不证明无条件分离，只定位错误推理缺失的“搜索”步骤。

语言 $L$ 属于 P，当且仅当其特征函数 ${\chi }_L(x)$（成员输出 1，非成员输出 0）属于 FP。这是判定接口在函数框架中的嵌入，不能把所有 FP 函数直接当成语言集合。

FNP理路搜索关系与 FNPFNP · Polynomially balanced search relation · 多项式平衡搜索关系用多项式平衡关系规定可接受见证，处理变长证书与无解返回，并证明前缀语言怎样借助NP完全判定器恢复见证。采用多值关系。说关系 $R$ “可在 FP 中求解”，通常是说存在一个 FP 选择函数，有解时返回合法见证、无解时返回独立标记。文献也常把这些可解关系整体叫 FP；读到“FP=FNP”时须按关系可解性的约定理解，不能把本页的单值函数集合与关系集合直接作字面相等。

Cook–Reckhow 证明系统理路Cook–Reckhow 命题证明系统Cook–Reckhow proof system · Propositional proof system以多项式时间可验证、恰好生成全部命题永真式为条件的抽象证明系统。使用 FP 函数把证明串映成永真式，其时间预算按证明输入的长度计算，不按公式长度计算。优化值与见证恢复理路从优化阈值到最优见证Optimization to threshold decision · Binary search for optimum · 优化搜索判定归约在有限整数目标和显式上界下二分求最优值，再用受阈值约束的前缀恢复见证，分开核算数值范围与编码成本。则把输出职责拆成最优整数和达到该值的对象；只有两个职责都完成，才算解决指定的优化输出函数或搜索任务。