A card from a free library — ask anything, no account, works offline. Every card carries its source.
Cobham 1965 — The intrinsic computational difficulty of functions
chain
A. Cobham (1965). The intrinsic computational difficulty of functions. Logic, Methodology and Philosophy of Science (Proc. 1964 Congress), North-Holland, 1965, 24–30. Cited by its record. License as found: cited by its record. What it gave the chain: feasible = polynomial in the LENGTH of the input, and the length of a number is its logarithm.
source
A. Cobham (1965), Logic, Methodology and Philosophy of Science (Proc. 1964 Congress), North-Holland, 1965, 24–30
card id
card_chain_cobham_1965
address
WIT.codex.FCT/the-intrinsic-computational-difficulty-of-functi/REF.WITNESSED@a-cobham
adjoining cards
- builds on → Briggs 1624 — Arithmetica logarithmica — feasible = polynomial in the LENGTH of the input, and the length of a number is its logari
- connects at → P versus NP — where the logarithm enters: the length of the input is the logarithm of the number; polyno
- builds on → Turing 1936 — On computable numbers, with an application to the Entscheidungsproblem — feasible = polynomial in the LENGTH of the input, and the length of a number is its logari
- enables → S. A. Cook 1971 — The complexity of theorem-proving procedures — a later work standing on an earlier one
Is this card incomplete? Tell the library — it will call out for more ↗