FPRD LabShare an approach

← Claims

Negative result · failed approach

FPRD-LRS-F01

Expanded-value powering is not a polynomial-time strategy

Exact statement

Repeated squaring does not yield a deterministic polynomial-time output-producing algorithm in the bit model: the order-one sequence (u_n=2^n) has (n+1) output bits when (n) is supplied in binary.

StatusProved output-size obstruction
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

Polynomially many arithmetic operations are not polynomial bit complexity when intermediate integers are exponentially long.

Hypotheses and scope

  • Runtime is measured in the standard Turing bit model.

Proof or evidence

The recurrence u_0=1 and u_{k+1}=2u_k has u_n=2^n. A binary n of length ℓ can therefore request an output with 2^{Θ(ℓ)} bits.

Output-size obstruction →

Verification notes

The record labels this only as an obstruction to explicit expansion, not as a hardness theorem for zeroness.

Limitations

  • The zero test for this example is trivial; output size alone does not rule out a compact deterministic zero test.

Open work

Keep compact circuit construction separate from exact integer expansion in future algorithms.