Home / Research Interests / Complexity


[a_appliedanalysis graphic]
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.  


[complexity cake graphic]
 


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


[dots and boxes graphic]




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

 

[amazons graphic]




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.