A card from a free library — ask anything, no account, works offline. Every card carries its source.
Baker 1975 — Relativizations of the P =? NP question
chain
T. Baker, J. Gill, R. Solovay (1975). Relativizations of the P =? NP question. SIAM J. Comput. 4 (1975) 431–442. DOI 10.1137/0204037. Canonical: https://doi.org/10.1137/0204037. Cited by its record. License as found: SIAM — publisher's copyright, cited. What it gave the chain: the first barrier: no relativizing proof can settle the question.
source
card id
card_chain_baker_gill_solovay_1975
address
WIT.codex.FCT/relativizations-of-the-p-np-question/REF.WITNESSED@t-baker-j-gill-r-solovay
adjoining cards
- builds on → S. A. Cook 1971 — The complexity of theorem-proving procedures — the first barrier: no relativizing proof can settle the question
- enables → Razborov 1997 — Natural proofs — the second barrier: natural proofs cannot, if one-way functions exist
Is this card incomplete? Tell the library — it will call out for more ↗