List of hard PCP instances

Size

Width

Instances

Length of shortest solution
Number of shortest solutions
Solving time (seconds)

3

3

 1001 0100 10
75
2
0.66
 011 1011 0110
55
1
0.08
 01 010 1101
44
1
0.06

4

 11011 011011 1110
252
1
35.37
 1011 101 0101101
216
1
22.98
 00110 001 1001
132
1
0.53
 10 101011 11011
119
1
0.22
 10 0011 10111
112
2
0.51

5

 111010110 1101 11011
240
1
2.31
 1101110110 1101 11101
216
1
43.30
 1110110110 1011 11101
216
1
31.80
 1101110110 0111 11101
216
2
43.39
 1101101100 01100 0011
216
1
31.28

4

3

 111110 0111 10100 011
302
1
33.45
 110011 1001 100 0110
273
1
109.37
 1111 10100 001 1011
240
1
18.55
 110001 1001 110 0110
217
1
2.20
 0000 0111 110 10100
204
1
1.06

4

 1010100 111011 01 010
256
1
15.82
 10000 010 1101 00001
206
1
0.34
 10101 0101111 11011 11001
200
1
7.45
 10111 11001 0011 01100
198
1
22.13
 11100 10111 1001 11101
193
2
0.50

Notes: The instances in blue came from [1][2]. Instances in red were found by my solver. The solving time shown in the table is approximate. The configurations of the machines running for experiments are, OS: Linux 2.4.7, CPU: Pentium 600, Memory: 128M. The compiler is gcc, with the option '-O3'.

[1]Richard J. Lorentz, Creating difficult instances of the Post Correspondence Problem, CG 2000, 2000.
[2]http://www.informatik.uni-leipzig.de/~pcp/pcpcontest_en.html

This webpage was created on April 29, 2001

Introduction
What's PCP?
PCP's theoretical place

Solving hard PCP instances
Bidirectional search
Cache scheme
Iterative deepening A*
Tail recursion removal

Instances having no solutions
Filters
Exclusion method
Pattern method

Hard instances list
The known hard instances
Data of the solutions

Documents
Presentation slides
Class project report
PCP instances