This document contains information about the:

The rules, specifications, and deadlines given here are absolute. Only the competition panel has the right to make exceptions.

The design and procedures of this CASC evolved from those of previous CASCs. Important changes for this CASC are:

- The division winners of the previous CASC are automatically entered into their divisions, to provide benchmarks against which progress can be judged. Previously, if any division was won by the system that won that division in the previous CASC, then no winner was announced in that division. This rule has been removed, so that the previous winner can again be proclaimed the winner.
- The SAT division has been divided into two classes, one ranked by the number of problems solved, and one ranked by the number of problems solved with acceptable model output.
- The numbers of problems in the categories in the various divisions is (roughly) proportional to the numbers of eligible problems than can be used in the categories after taking into account the limitation on very similar problems.
- In the MIX and SAT divisions, if a system wins both the Assurance and Proof/Model class, then a single unannotated trophy will be awarded.

- ATP systems can be entered at only the division level.
- ATP systems can be entered into more than one division. A system that is not entered into a division is assumed to perform worse than the entered systems, for that type of problem.
- The ATP systems have to run on a single locally provided standard UNIX
workstation (the
*general hardware*). ATP systems that cannot run on the general hardware can be entered into the demonstration division.

- The
**MIX**division: Mixed CNF really non-propositional theorems

*Mixed*means Horn and non-Horn problems, with or without equality, but not unit equality problems (see the UEQ Division below).*Really non-propositional*means with an infinite Herbrand universe. The MIX Division has five problem categories:- The
**HNE**category: Horn with No Equality - The
**HEQ**category: Horn with some (but not pure) Equality - The
**NNE**category: Non-Horn with No Equality - The
**NEQ**category: Non-Horn with some (but not pure) Equality - The
**PEQ**category: Pure Equality

- The
**Assurance**class: Ranked according to the number of problems solved (a "yes" output, giving an*assurance*of the existence of a proof). - The
**Proof**class: Ranked according to the number of problems solved with an acceptable proof output on`stdout`. The competition panel judges whether or not each system's proof format is*acceptable*.

- The
- The
**FOF**division: Mixed FOF non-propositional theorems

The FOF Division has two problem categories:- The
**FNE**category: FOF with no Equality - The
**FEQ**category: FOF with Equality

- The
- The
**SAT**division: Mixed CNF really non-propositional non-theorems

The SAT Division has two problem categories:- The
**SNE**category: SAT with No Equality - The
**SEQ**category: SAT with Equality

- The
**Assurance**class: Ranked according to the number of problems solved (a "yes" output, giving an*assurance*of the existence of a model). - The
**Model**class: Ranked according to the number of problems solved with an acceptable model output on`stdout`. The competition panel judges whether or not each system's model format is*acceptable*.

- The
- The
**EPR**division: CNF effectively propositional theorems and non-theorems

*Effectively propositional*means non-propositional with a finite Herbrand Universe. The EPR Division has two problem categories:- The
**EPT**category: Effectively Propositional Theorems (unsatisfiable clause sets) - The
**EPS**category: Effectively Propositional non-theorems (Satisfiable clause sets)

- The
- The
**UEQ**division: Unit equality CNF really non-propositional theorems

The entry specifies which competition divisions' problems are to be used. The results are presented along with the competition divisions' results, but may not be comparable with those results.

- Intel P3 993MHz CPU
- 512MB memory
- Linux 2.4.9-34 operating system

The problems are from the TPTP Problem Library. The TPTP version used for the competition is not released until after the system installation deadline.

The problems have to meet certain criteria to be eligible for selection:

- The TPTP uses system performance data to compute problem difficulty
ratings, and from the ratings classifies problems as one of:
- Easy: Solvable by all state-of-the-art ATP systems
- Difficult: Solvable by some state-of-the-art ATP systems
- Unsolved: Not yet solved by any ATP system
- Open: Theorem-hood unknown

- The TPTP distinguishes versions of problems as one of standard, incomplete, augmented, especial, or biased. All except biased problems are eligible.

- The selection is constrained so that no division or category contains an excessive number of very similar problems.
- The selection mechanism is biased to select problems that are new in the TPTP version used, until 50% of the problems in each category have been selected, after which random selection (from old and new problems) continues. The actual percentage of new problems used depends on how many new problems are eligible and the limitation on very similar problems.

*Number of Problems*

The minimal numbers of problems that have to be used in each division and
category, to ensure sufficient confidence in the competition results,
are determined from the numbers of eligible problems in each division
and category
(the competition organizers have to ensure that there is sufficient CPU time
available to run the ATP systems on this minimal number of problems).
The minimal numbers of problems are used in determining the
CPU time limit imposed on each solution
attempt.

A lower bound on the total number of problems to be used is determined from the number of workstations available, the time allocated to the competition, the number of ATP systems to be run on the general hardware over all the divisions, and the CPU time limit, according to the following relationship:

Number of workstations * Time allocated Number of problems = --------------------------------------- Number of ATP systems * CPU time limitIt is a lower bound on the total number of problems because it assumes that every system uses all of the CPU time limit for each problem. Since some solution attempts succeed before the CPU time limit is reached, more problems can be used.

The numbers of problems used in the categories in the various divisions is (roughly) proportional to the numbers of eligible problems than can be used in the categories, after taking into account the limitation on very similar problems.

The numbers of problems used in each division and category are determined according to the judgement of the competition organizers.

- rename all predicate and function symbols to meaningless symbols
- randomly reorder the clauses and literals in CNF problems
- randomly reorder the formulae in FOF problems
- randomly reverse the unit equalities in the UEQ problems
- remove equality axioms that are not needed by some of the ATP systems
- add equality axioms that are needed by some of the ATP systems
- output the problems in the formats required by the ATP systems
(The clause type information, one of
`axiom`

,`hypothesis`

, or`conjecture`

, may be included in the final output of each formula.)

`CCCNNN-1.p`

for the symbolic links, with `NNN`

running from `001`

to the number of problems in the respective
division or category.
The problems are specified to the ATP systems using the symbolic link
names.
In the demonstration division the same problems are used as for the competition divisions, with the same tptp2X transformations applied. However, the original file names can be retained.

In the demonstration division, each entrant can choose to use either a CPU or a wall clock time limit, whose value is the CPU time limit of the competition divisions.

During the competition, for each ATP system, for each problem attempted,
three items of data are recorded:
whether or not a solution was found,
the CPU time taken,
and whether or not a solution (proof or model) was output on `stdout`.
In the MIX division proof class and the SAT division model class, the systems
are ranked according to the number of problems solved with an acceptable
solution output.
In all other cases the systems
are ranked according to the numbers of problems solved.
If there is a tie according to these rankings then the tied systems are
ranked according to their average CPU times over problems solved.
Division and class winners are announced and prizes are awarded.

At some time after the competition all high ranking systems in each division are tested over the entire TPTP. This provides a final check for soundness. If a system is found to be unsound, and it cannot be shown that the unsoundness did not manifest itself in the competition, then the system is retrospectively disqualified. At some time after the competition the proofs from the winner of the MIX division proof class, and the models from the winner of the SAT division model class, are checked by the panel. If any of the proofs or models are unacceptable, i.e., they are significantly worse than the samples provided, then that system is retrospectively disqualified. All disqualifications are reported in the journal paper about the competition.

The precomputation and storage of any information specifically about TPTP problems is not allowed. Strategies and strategy selection based on the characteristics of a few specific TPTP problems is not allowed, i.e., strategies and strategy selection must be general purpose and expected to extend usefully to new unseen problems. If automatic strategy learning procedures are used, the learning must ensure that sufficient generalization is obtained, and that no learning at the individual problem level is performed.

For every problem solved, the system's solution process has to be reproducible by running the system again.

With the exception of the MIX division proof class and the SAT division
model class, the ATP systems are not required to output solutions (proofs
or models).
However, systems that do output solutions to `stdout`

are
highlighted in the presentation of results.

Entrants must install their systems on the general hardware, and ensure that their systems execute in the competition environment, according to the checks listed below. Entrants are advised to perform these checks well in advance of the system installation deadline. This gives the competition organizers time to help resolve any difficulties encountered.

- Check: The ATP system can be run by an absolute path to the executable.
For example:
prompt> pwd /home/tptp prompt> which MyATPSystem /home/tptp/bin/MyATPSystem prompt> /home/tptp/bin/MyATPSystem /home/tptp/TPTP/Problems/PUZ/PUZ031-1.p Proof found in 147 seconds.

- Check: The ATP system accepts an absolute path name for a symbolic
link as the problem file name. For example:
prompt> cd /home/tptp/tmp prompt> ln -s /home/tptp/TPTP/Problems/PUZ/PUZ031-1.p CCC001-1.p prompt> cd /home/tptp prompt> /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p Proof found in 147 seconds.

- Check: The ATP system makes no assumptions about the format of the
problem file name. For example:
prompt> cp /home/tptp/TPTP/Problems/PUZ/PUZ031-1.p _foo-Blah prompt> /home/tptp/bin/MyATPSystem _foo-Blah Proof found in 147 seconds.

- Check: The ATP system can run under the
`TreeLimitedRun`program. For example:prompt> which TreeLimitedRun /home/tptp/bin/TreeLimitedRun prompt> /home/tptp/bin/TreeLimitedRun -q0 200 400 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: /home/tptp/bin/MyATPSystem TreeLimitedRun: CPU time limit is 200s TreeLimitedRun: WC time limit is 400s TreeLimitedRun: PID is 4867 TreeLimitedRun: ---------------------------------------------------------- Proof found in 147 seconds. FINAL WATCH: 147.8 CPU 150.0 WC

- Check: The ATP system's CPU time can be limited using the TreeLimitedRun
program.
For example:
prompt> /home/tptp/bin/TreeLimitedRun -q0 10 20 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: /home/tptp/bin/MyATPSystem TreeLimitedRun: CPU time limit is 10s TreeLimitedRun: WC time limit is 20s TreeLimitedRun: PID is 5827 TreeLimitedRun: ---------------------------------------------------------- CPU time limit exceeded FINAL WATCH: 10.7 CPU 13.1 WC

- Check: The ATP system's wall clock time can be limited using the
`TreeLimitedRun.c`

program. For example:prompt> /home/tptp/bin/TreeLimitedRun -q0 20 10 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: /home/tptp/bin/MyATPSystem TreeLimitedRun: CPU time limit is 20s TreeLimitedRun: WC time limit is 10s TreeLimitedRun: PID is 5827 TreeLimitedRun: ---------------------------------------------------------- Alarm clock FINAL WATCH: 9.7 CPU 10.1 WC

`stdout`

indicating the result, one of:
- A solution exists (for CNF problems, the clause set is unsatisfiable, for FOF problems, the conjecture is a theorem)
- No solution exists (for CNF problems, the clause set is satisfiable, for FOF problems, the conjecture is a non-theorem)
- No conclusion reached.

- Check: The system outputs a distinguished string when terminating of
its own accord.
For example, here the entrant has specified that the distinguished string
`Proof found`

indicates that a solution exists. If appropriate, similar checks should be made for the cases where no solution exists and where no conclusion is reached.prompt> /home/tptp/bin/TreeLimitedRun -q0 200 400 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: /home/tptp/bin/MyATPSystem TreeLimitedRun: CPU time limit is 200s TreeLimitedRun: WC time limit is 400s TreeLimitedRun: PID is 5827 TreeLimitedRun: ---------------------------------------------------------- Proof found in 147 seconds. FINAL WATCH: 147.8 CPU 150.0 WC

- Check: The system outputs distinguished strings at the start and end
of its solution.
For example, here the entrant has specified that the distinguished strings
`START OF PROOF`

and`END OF PROOF`

identify the start and end of the solution.prompt> /home/tptp/bin/TreeLimitedRun -q0 200 400 /home/tptp/bin/MyATPSystem -output_proof /home/tptp/tmp/CCC001-1.p TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: /home/tptp/bin/MyATPSystem TreeLimitedRun: CPU time limit is 200s TreeLimitedRun: WC time limit is 400s TreeLimitedRun: PID is 5827 TreeLimitedRun: ---------------------------------------------------------- Proof found in 147 seconds. START OF PROOF ... acceptable proof here ... END OF PROOF FINAL WATCH: 147.8 CPU 150.0 WC

`/tmp`

.
Multiple copies of the ATP systems have to be executable concurrently on different machines but in the same (NFS cross mounted) directory. It is therefore necessary to avoid producing temporary files that do not have unique names, with respect to the machines and other processes. An adequate solution is a file name including the host machine name and the process id.

For practical reasons excessive output from the ATP systems is not allowed.
A limit, dependent on the disk space available, is imposed on the amount
of `stdout`

and `stderr`

output that can be produced.
The limit is at least 10KB per problem (averaged over all problems so
that it is possible to produce *some* long proofs).

- Check: No temporary or other files are left if the system terminates
of its own accord, and no temporary or other files are left anywhere
other than in
`/tmp`

if the system is terminated by a`SIGXCPU`or`SIGALRM`. Check in the current directory, the ATP system's directory, the directory where the problem's symbolic link is located, and the directory where the actual problem file is located.prompt> pwd /home/tptp prompt> /home/tptp/bin/TreeLimitedRun -q0 200 400 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: /home/tptp/bin/MyATPSystem TreeLimitedRun: CPU time limit is 200s TreeLimitedRun: WC time limit is 400s TreeLimitedRun: PID is 13526 TreeLimitedRun: ---------------------------------------------------------- Proof found in 147 seconds. FINAL WATCH: 147.8 CPU 150.0 WC prompt> ls /home/tptp ... no temporary or other files left here ... prompt> ls /home/tptp/bin ... no temporary or other files left here ... prompt> ls /home/tptp/tmp ... no temporary or other files left here ... prompt> ls /home/tptp/TPTP/Problems/PUZ ... no temporary or other files left here ... prompt> ls /tmp ... no temporary or other files left here by decent systems ...

- Check: Multiple concurrent executions do not clash. For example:
prompt> (/home/tptp/bin/TreeLimitedRun -q0 200 400 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p) & (/home/tptp/bin/TreeLimitedRun -q0 200 400 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p) TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: /home/tptp/bin/MyATPSystem TreeLimitedRun: CPU time limit is 200s TreeLimitedRun: WC time limit is 400s TreeLimitedRun: PID is 5827 TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: ---------------------------------------------------------- TreeLimitedRun: /home/tptp/bin/MyATPSystem TreeLimitedRun: CPU time limit is 200s TreeLimitedRun: WC time limit is 400s TreeLimitedRun: PID is 5829 TreeLimitedRun: ---------------------------------------------------------- Proof found in 147 seconds. FINAL WATCH: 147.8 CPU 150.0 WC Proof found in 147 seconds. FINAL WATCH: 147.8 CPU 150.0 WC

`.tar.gz`

file containing
the system source code, any other files required for installation, and
a `ReadMe`

file.
The `ReadMe`

file must contain:
- Instructions for installation
- Instructions for executing the system
- Format of problem files, in the form of
`tptp2X`format and transformation parameters. - Command line, using
`%s`and`%d`to indicate where the problem file name and CPU time limit must appear.

- Format of problem files, in the form of
- The distinguished strings output to indicate
- The result
- The start of solution output
- The end of solution output

The installation procedure may require changing path variables, invoking
`make`

or something similar, etc, but nothing unreasonably
complicated.
All system binaries must be created in the installation process; they
cannot be delivered as part of the installation package.
The system is reinstalled onto the general hardware by the competition
organizers, following the instructions in the `ReadMe`

file.
Installation failures before the installation deadline are passed
back to the entrant.
After the installation deadline access to the general hardware is
denied, and no further changes or late systems are accepted
(i.e., deliver your installation package before the installation deadline
so if the installation fails you have a chance to fix it!).
If you are in doubt about your installation package or procedure, please
email the competition organizers.

For systems running on entrant supplied hardware in the demonstration division the systems are installed on the respective hardware by the entrants.

`perl`

script, provided by the competition organizers.
The jobs are queued onto the workstations so that each
workstation is running one job at a time.
All attempts at the Nth problems in all the divisions and
categories are started before any attempts at the (N+1)th problems.
During the competition a `perl`

script parses the systems'
outputs.
If any of an ATP system's distinguished strings are found then the CPU
time used to that point is noted.
A system has solved a problem iff it outputs its "success" string within the
CPU time limit, and a system has produced a proof iff it outputs its
"end of solution" string within the CPU time limit.
The result and timing data is used to generate an HTML file, and a WWW
browser is used to display the results.

The execution of the demonstration division systems is supervised by their entrants.

Entering many similar versions of the same system is deprecated, and entrants may be required to limit the number of system versions that they enter. The division winners from the previous CASC are automatically entered into their divisions, to provide benchmarks against which progress can be judged. Systems entered in the MIX division are automatically ranked in the assurance class, and are ranked in the proof class if they output acceptable proofs. Systems entered in the SAT division are automatically ranked in the assurance class, and are ranked in the model class if they output acceptable models. After the competition all systems' source code is made publically available on the CASC WWW site.

It is assumed that each entrant has read the WWW pages related
to the competition, and has complied with the competition rules.
Non-compliance with the rules could lead to disqualification.
A "catch-all" rule is used to deal with any unforseen circumstances:
*No cheating is allowed*.
The panel is allowed to disqualify entrants due to unfairness, and to adjust
the competition rules in case of misuse.

- Architecture. This section introduces the ATP system, and describes the calculus and inference rules used.
- Implementation. This section describes the implementation of the ATP system, including the programming language used, important internal data structures, and any special code libraries used.
- Strategies. This section describes the search strategies used, why they are effective, and how they are selected for given problems. Any strategy tuning that is based on specific problems' characteristics must be clearly described (and justified in light of the tuning restrictions).
- Expected competition performance. This section makes some predictions about the performance of the ATP system in each of the divisions and categories in which the system is competing.
- References.

The competition panel decides whether or not the proofs and models are acceptable.