Identifying instances of no solutions
In overview, a great portion of instances has no solutions at all. Some of them can be easily identified, while some need to go through quite complicated procedures. When configurations always prolong, the solver will never find the solutions and the instance will be left as unsolved one. However, it is possible that at the beginning, we can prove it in fact can not have solutions. The following four methods can help us to identify some of those instances.

Filters
Filters are raised by Richard Lorentz. The following explanations ignore the cases when the up string and the down string are identical in one pair. There are three types of filters:

Type 1: Prefix/Postfix filter
If an instance has solutions, it must have one pair where one string is another's prefix and another pair where one string is another's postfix. This condition ensures the solution can start at one pair and end at one pair.

Type 2: Length balance filter
If an instance has solutions, it must have one pair whose top string is longer than its bottom string and another pair whose bottom string longer than its top string. This condition ensures the configuration has the chance to shrink.

Type 3: Element balance filter
If all pairs are used in the solution, then when there is one pair whose top string has more element 1 than the corresponding bottom string has, there must exist another pair whose bottom string has more 1 than the top one. This conditions ensures the number of 1's in the configuration can be decreased. The same rule applies to element 0.

Masks
Masks can also be used to identify instances having no solution. When an instance has both upmask and downmask, it definitely has no solution. Cooperated with other methods, masks can help the solver find many instances of no solutions.

Exclusion method
In some instances, when the solver starts at one pair, the following selections can only among some pairs, not all pairs. The impossible pairs then can be removed whenever the starting pair is the one causing the exclusion. The exclusion method deals with how to find such excluded pairs.

Pattern method
When a configuration has one substing such that in all possible paths of selections, this substring will always occur, then this substring can never be removed. This property tells us that this instance has no solution. The substring is called pattern and it may have four types of forms: the prefix pattern, the postfix pattern, the infix pattern, and the prefix&postfix pattern.




This webpage was created on April 29, 2001
Last modified on September 10, 2001 by Ling Zhao

    

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?