|
 |
||||||||||||||||||
Next step
Instances unsolved Here are the three instances that we can not solve. Though we strongly feel they all have no solutions, but based on our knowledge, we can not prove it. Probably they contain very complicated pattern, or we need to find some new tools to tackle them.
Notes: PCP 14 has been proved of no solution by Prof. Richard Lorentz. Because the length difference in every pair is even, all possible configurations generated should be even. Once understaning this point, we can use downmask to show it has no solutions. I have proved PCP 13 has no solutions. If the selection starts at pair 2, there will be a '001' prefix pattern. Hence, we can not begin at this pair. On the other hand, in the reverse of this instance, the selection can not end with this pair. After some simple analysis on the reverse form, it turns out to be of no solutions. Pattern method implementation It is possible to incorporate the pattern method into the solver, but it may be very difficult. How to make the computer deduce as the human being does? Maybe we need some machine learning techniques to fulfill it. Where are the applications? Though PCP has simple definition and many nice properties, its solver is discussed very little in the literature. One reason is the lack of applications in the real world. We are eager to find them! Some conjectures In Lorentz's paper, it conjectured that the instance with shortest length 75 is the hardest one in all instances having size 3 and width 3. Now we have checked all instances except PCP(12), which is still unsolved. There is only one step before we ascertain this conjecture.
This webpage was created on April 29, 2001
Last modified on September 10, 2001 by Ling Zhao |
Introduction
Solving hard PCP instances
Instances having no solutions
Hard instances list
Documents
Next step
Contact |
|||||||||||||||||
