List of hard PCP instances

Size

Width

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

3

3
100
1		 0
100		 1
0
75
2
0.66
01
1		 1
011		 011
0
55
1
0.08
0
1		 01
0		 1
101
44
1
0.06

4
1101
1		 0110
11		 1
110
252
1
35.37
101
1		 1
01		 010
1101
216
1
22.98
0011
0		 00
1		 1
001
132
1
0.53
1
0		 10
1011		 1101
1
119
1
0.22
1
0		 0
011		 1011
1
112
2
0.51

5
11101
0110		 110
1		 1
1011
240
1
2.31
11011
10110		 110
1		 1
1101
216
1
43.30
11101
10110		 101
1		 1
1101
216
1
31.80
11011
10110		 011
1		 1
1101
216
2
43.39
11011
01100		 0110
0		 0
011
216
1
31.28

4

3
111
110		 011
1		 10
100		 0
11
302
1
33.45
110
011		 100
1		 1
00		 0
110
273
1
109.37
111
1		 10
100		 00
1		 1
011
240
1
18.55
110
001		 100
1		 1
10		 0
110
217
1
2.20
000
0		 0
111		 11
0		 10
100
204
1
1.06

4
1010
100		 11
1011		 0
1		 01
0
256
1
15.82
1000
0		 01
0		 1
101		 00
001
206
1
0.34
1010
1		 010
1111		 1
1011		 110
01
200
1
7.45
1011
1		 11
001		 0
011		 0110
0
198
1
22.13
1110
0		 10
111		 10
01		 1
1101
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
Last modified on Feb 16, 2002 by Ling Zhao

    

Introduction
What's PCP?
PCP's theoretical place

Solving hard PCP instances
Masks
Bidirectional search
Cache scheme
Iterative deepening A*
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
Class project report
PCP instances
Links

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

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