Квантовые вычисления со времен Демокрита - Скотт Ааронсон

http://www.scottaaronson.com/papers/philos.pdf

21

«Мыслю — следовательно, существую» (лат.) — Прим. пер.

22

См.: David J. Chalmers, The Conscious Mind: In Search of a Fundamental Theory, Oxford University Press, 1997.

23

http://www.ams.org/notices/199607/marker.pdf

24

A. Burdman Fefferman and S. Fefferman, Alfred Tarski: Life and Logic (Cambridge: Cambridge University Press, 2008).

25

http://www.complexityzoo.com

26

A. Stothers, On the complexity of matrix multiplication. Unpublished PhD Thesis, University of Edinburgh (2010). http://www.maths.ed.ac.uk/pg/thesis/stothers.pdf

27

V. Vassilevska Williams, Breaking the Coppersmith — Winograd barrier. In Proceedings of Annual ACM Symposium on Theory of Computing (2012). http://www.cs.berkeley.edu/~virgi/matrixmult.pdf

28

http://www.ioccc.org/

29

См: Saul Kripke, Naming and Necessity, Wiley-Blackwell, 1991 (reprint edition).

30

См.: http://www.claymath.org/millennium/

31

То есть останавливается в принимающем состоянии. — Прим. пер.

32

W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Annals of Mathematics 2:139 (1994), 703–722. http://www.math.dartmouth.edu/∼carlp/PDF/paper95.pdf

33

M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P, Annals of Mathematics 160:2 (2004), 781–793. http://www.cse.iitk.ac.in/users/manindra/algebra/primalityv6.pdf

34

J. Gill, Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing 6:4 (1977), 675–695.

35

Исход президентских выборов в США в ноябре 2000 г. зависел от того, на чью сторону встанут выборщики от штата Флорида, а там количество проголосовавших за Альберта Гора и за Джорджа Буша (сына) различалось всего на несколько десятков голосов. На то, чтобы установить волю избирателей, потребовалось несколько недель, и половину Америки результат подсчета не убедил. — Прим. пер.

36

Крупные центры игорного бизнеса. — Прим. пер.

37

http://www.cs.berkeley.edu/∼luca/cs278-01/notes/lecture9.ps

38

R. M. Karp and R. J. Lipton, Turing machines that take advice, L'Enseignement Mathematique 28 (1982), 191–209.

39

R. Impagliazzo and A. Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In Proceedings of ACM Symposium on Theory of Computing (New York: ACM, 1997), pp. 220–9.

40

V. Kabanets and R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13:1/2 (2004), 1–46.

41

D. Kahn, The Codebreakers (New York: Scribner, 1996).

42

См.: http://en.wikipedia.org/wiki/Pizzino.

43

Ну хорошо. Если вы жаждете увидеть доказательство, то его, например, можно найти в: Oded Goldreich, Foundations of Cryptography (Volume I: Basic Tools), Cambridge University Press, 2007.

44

L. Blum, M. Blum and M. Shub, A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, 15 (1996), 364–383. (Заметьте, что первый из авторов — женщина. — Прим. пер.).

45

M. Ajtai and C. Dwork, A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of 29th Annual ACM Symposium on Theory of Computing (New York: ACM, 1997), pp. 284–93.

46

O. Regev, On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56:6 (2009), 1–40.

47

J. Håstad, R. Impagliazzo, L. A. Levin and M. Luby, A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28:4 (1999), 1364–96. http://citeseer.ist.psu.edu/hastad99pseudorandom.html

48

A. Chi-Chih Yao, Theory and applications of trapdoor functions [extended abstract]. In Proceedings of 24th Annual IEEE Symposium on Foundations of Computer Science (Silver Spring, MD: IEEE Computer Society Press, 1982), pp. 80–91.

49

См.: Martin Gardner, Penrose Tiles to Trapdoor Ciphers: And the Return of Dr. Matrix, Mathematical Association of America, 1997.

50

http://citeseer.ist.psu.edu/340126.html

51

http://www.cs.tau.ac.il/∼odedr/papers/qcrypto.pdf

52

C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem [extended abstract]. In Proceedings of Annual ACM Symposium on Theory of Computing (New York: ACM, 2009), pp. 333–42.

53

C. Gentry, Fully homomorphic encryption using ideal lattices. In Proceedings of Annual ACM Symposium on Theory of Computing (New York: ACM, 2009), pp. 169–78.

54

Американский математик британского происхождения, доказавший Великую теорему Ферма. — Прим. пер.

55

http://www.scottaaronson.com/papers/island.pdf

56

Числовое поле F называется «алгебраически замкнутым», если любое алгебраическое уравнение, в котором задействованы числа из F, может быть решено тоже с использованием чисел из F (исключением являются тривиальные нерешаемые уравнения вроде 0 = 1). Чтобы проиллюстрировать это определение, скажем, что рациональные числа не являются алгебраически замкнутыми, поскольку уравнение x2 = 2 имеет только иррациональные решения; даже действительные числа алгебраически не замкнуты, поскольку уравнение x2 = — 1 имеет только мнимые решения. Но в начале XIX века был установлен важный факт: комплексные числа алгебраически замкнуты. Априори можно было предположить, что нам придется изобретать бесконечную пирамиду все более сложных чисел, чтобы с их помощью решать уравнения с числами предыдущего уровня сложности. Но нет, все закончилось на комплексных числах! К примеру, решением