Master thesis: Solving and Creating Difficult Instances of Post's Correspondence Problem
Presentation slides
  • As a part of CMPUT657 Heuristic Search course, I gave a presentation for Richard Lorentz's paper titled "Creating Difficult Instances of the Post Correspondence Problem" on March 20, 2001. This is the revised version of the slides.

  • The following is the slides I used to give a presentation on "Tackling Post's Correspondence Problem" in the regular GAMES group meeting at the University of Alberta on July 31,2001.


PCP instances
  • The 23 hard instances in the records: here
  • The 200 hard instances used in the experiments of my thesis: here
  • The 3,170 instances in PCP[3,4] unsolved by my PCP solver: here
  • The 13,923 instances in PCP[4,3] unsolved by my PCP solver: here

Links
   

Introduction
What's PCP?
PCP's theoretical place

Solving hard PCP instances
Masks
Bidirectional probing
Heuristic pruning
Cache scheme
Depth-first iterative deepening
Tail recursion removal

Instances having no solutions
Filters
Masks
Exclusion method
Pattern method

Hard instances list
The known hard instances
Data of the solutions

Documents
Presentation slides
PCP Instances
Links

Next step
Instances unsolved
Pattern method implementation
Where are the applications?
Some conjectures

Contact
Who am I?
Why am I so interested?
How to contact?