4 ms·
Not true. You can just use the characterization of NP in terms of certificates and deterministic verifying machines, and still get everything (except maybe the
by j2kun 13y ago
Not true. You can just use the characterization of NP in terms of certificates and deterministic verifying machines, and still get everything (except maybe the standard proof of the Karp-Lipton theorem).
- diminish 13y agoWatch out where you stand. Sons of Turing are a large mafia, which will immediately reduce every other computational construct into TMs and claim you didn't really add up anything :)
- j2kun 13y agoTell that to the Quantum Brotherhood. Edit: you may find the head of a cat in your bed, but only if you look and only with probability 1/2.