Saturday, March 19, 2005

Unsolved instance of the Post Correspondance Problem

{(10,0),(0,001),(001,1)} Ling Zhao's PCP page

Prove it has no solution...
Also given in bit-flipped form as (6.15) in his Master's thesis: {(110,1), (1,01), (0, 110)}

No comments :