Complexity

The fundamental problems of Coding Theory are provably hard.

Berlekamp, E.R., R.J. McEliece, and H.C.A. Van Tilborg, 1978, "On The Inherent Intractability
Of Certain Coding Problems", IEEE Trans. Inform. Theory, IT 24:384-386.

That paper very soon led McEliece to design a cryptographic scheme which is provably hard to break.

McEliece, R.J., "A Public-Key Cryptosystem Based on Algebraic Coding Theory", JPL DSN
Progress Report 42-44, pp. 114-116, Jan-Feb 1978.

The game of LR Hackenbush is NP.
Pages 211-217 of Winning Ways volume 1 second edition, A K Peters Ltd, January 2003.

Loony Dots-and-Boxes endgames are NP.
Pages 577-578 of Winning Ways volume 3 second edition, A K Peters Ltd, August 2003.

Some games with very simple orthodox strategies have complex canonical forms. Pages 26-28 of Sums of Nx2 Amazons, by Elwyn Berlekamp, Institute of Mathematics Statistics "Lecture Notes -- Monograph Series", 35:1-34, 2000.

	Home / Research Interests / Complexity
Home Publications Videos Research Interests Algorithms Applied Analysis Games Complexity Computer Architecture Finance Business Information Theory Philanthropy Thesis Students Awards Board Memberships K-12 Outreach Education / Employment Biographies Contact Information and Site Credits Site Map	Complexity The fundamental problems of Coding Theory are provably hard. Berlekamp, E.R., R.J. McEliece, and H.C.A. Van Tilborg, 1978, "On The Inherent Intractability Of Certain Coding Problems", IEEE Trans. Inform. Theory, IT 24:384-386. That paper very soon led McEliece to design a cryptographic scheme which is provably hard to break. McEliece, R.J., "A Public-Key Cryptosystem Based on Algebraic Coding Theory", JPL DSN Progress Report 42-44, pp. 114-116, Jan-Feb 1978. The game of LR Hackenbush is NP. Pages 211-217 of Winning Ways volume 1 second edition, A K Peters Ltd, January 2003. Loony Dots-and-Boxes endgames are NP. Pages 577-578 of Winning Ways volume 3 second edition, A K Peters Ltd, August 2003. Some games with very simple orthodox strategies have complex canonical forms. Pages 26-28 of Sums of Nx2 Amazons, by Elwyn Berlekamp, Institute of Mathematics Statistics "Lecture Notes -- Monograph Series", 35:1-34, 2000.