The CADE-16 ATP System Competition

Design and Organization

This document contains information about the:

Divisions
- Competition Divisions
- Demonstration Divisions
Infrastructure
Entry Requirements and Procedures
Performance Evaluation

The design and procedures of CASC-16 evolved from those of CASC-13, CASC-14, and CASC-15. The rules, deadlines, and specifications given here, are absolute. Only the competition panel has the right to make exceptions.

Disclaimer

Every effort has been made to organize the competition in a fair and constructive manner. No responsibility will be taken if, for one reason or the other, your system does not win.

Divisions

CASC-16 is divided into divisions according to problem and system characteristics. There are four competition divisions in which the systems are explicitly ranked, and one demonstration division in which systems can demonstrate their abilities without being formally ranked.

Competition Divisions

The MIX Division: Mixed CNF Non-Propositional Theorems
Mixed means Horn and non-Horn problems, with or without equality, but not unit equality problems (see the UEQ Division below). The MIX Division is divided into five 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 UEQ Division: Unit Equality CNF Non-Propositional Theorems
The SAT Division: Mixed CNF Non-Propositional Non-theorems
The FOF Division: Mixed FOF Non-Propositional Theorems
The FOF Division is divided into two categories:
- The FNE Category: FOF with no Equality
- The FEQ Category: FOF with Equality

The Problems section explains what problems are eligible for use in each division and category.

Entry into the competition divisions is subject to the following rules:

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 particular division is assumed to be useless 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 enter into the Special Hardware Division.

Demonstration Division

The SHW Division: Special Hardware
ATP systems that cannot run on the general hardware can enter into the Special Hardware Division. The hardware can be supplied by the entrant. The entry specifies which general hardware division's problems are to be used. The results will be presented along with the general hardware division's results, but may not be comparable with those from the systems that ran on the general hardware.

Infrastructure

Hardware and Software

The competition will be run on 10 SUN Ultra10 workstations, each having:

A 333MHz UltraSparc-II CPU
2MB cache
256MB memory
Solaris 2.6 HW 5/98 operating system

Problems

Problem Selection
The problems will be selected from the TPTP Problem Library, v2.2.1. The problems have to meet certain criteria to be eligible for selection:

The TPTP uses system performance data to classify problems as one of:
- Easy: Solvable by all state-of-the-art contributor ATP systems
- Difficult: Solvable by some state-of-the-art contributor ATP systems
- Unsolved: Solvable by no ATP systems
- Open: Theorem-hood unknown
Difficult problems will be eligible. Note: Entrants are encouraged to submit their latest system performance data to the collection, to help ensure that problems have appropriate ratings. Entrants will benefit from contributing their latest system performance data, as it ensures that problems that their system can solve are eligible (unless they are easy problems). The deadline for submitting data to be taken into account for CASC-16 is 14th June 1999.
The TPTP distinguishes versions of problems as one of standard, incomplete, augmented, especial, or biased. Standard and especial problems will be eligible.
No division or category will contain an excessive number of very similar problems.

The problems used will be randomly selected from the eligible problems at the start of the competition, based on a seed supplied by the competition panel.

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, will be 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). This minimal numbers of problems will then be used in determining the time limit imposed on each solution attempt.

A lower bound on the total number of problems that will be used will be 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 time limit, according to the following relationship:

                     Number of workstations * Time allocated
Number of problems = ---------------------------------------
                        Number of ATP systems * Time limit

It is a lower bound on the total number of problems because it assumes that every system will use all the time limit for each problem. Since some solution attempts will obviously succeed before the time limit is reached, more problems can actually be used. The actual numbers used in each division and category will be determined according to the judgement of the competition organizers.

Problem Preparation
It is necessary to ensure that no system receives an advantage or disadvantage due to the specific presentation of the problems in the TPTP. To this end the tptp2X utility, distributed with the TPTP, will be used to:

replace all predicate and function symbols by meaningless symbols,
randomly reorder the clauses and literals in CNF problems,
randomly reorder the formulae in FOF problems,
randomly reverse the unit equalities in 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.

Further, to prevent systems from recognizing problems from their file names, symbolic links will be made to the selected problems, using names of the form 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 will be specified to the ATP systems using the symbolic link names.

In the Special Hardware Division the same problems will be used as for the general hardware, with the same tptp2X transformations applied. However, the original file names will be retained.

Time Limits and Timing

A time limit will be imposed on each solution attempt. On the general hardware a CPU time limit will be imposed, while in the Special Hardware Division the entrant can choose to use either a CPU or a wall clock time limit.

A minimal time limit of 180 seconds will be used. The maximal time limit will be determined using the relationship used for determining the number of problems, with the minimal number of problems as the "Number of problems". The time limit will be chosen as a reasonable value within the range allowed.

The timing will be done by the UNIX /usr/bin/time command, which returns times in units of 0.1 second. If an ATP system cannot solve a problem, the runtime will be set to the time limit.

On the general hardware a wall clock time limit will be imposed in addition to the CPU time limit, in order to prevent very high memory usage that causes swapping. The wall clock time limit will be double the CPU time limit.

Entry Requirements and Procedures

System registration for CASC-16 will close 7th June 1999, and no registrations will be accepted after the deadline. For each system entered, a person has to be nominated to handle all issues (including execution difficulties) arising before and during the competition. The nominated entrant must formally register for CASC-16, using the CADE-16 registration form. However, it is not necessary for entrants to physically attend the competition.

Entering many similar versions of the same system is deprecated. Entrants may be required to limit the number of system versions that they enter. Winners are expected to provide public access to their system's source code.

It is assumed that each entrant has read all 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.

System Description

A system description has to be provided for each ATP system entered. The system descriptions, along with information regarding the competition design and procedures, will form the proceedings for the competition. The system descriptions must fit onto a single A4 page, using this LaTeX schema. The schema has the following sections:

Architecture. This section introduces the ATP system, and describes the calculus, inference rules, and search control 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.
Expected competition performance. This section should make some prediction about the performance of the ATP system in each of the divisions and categories the system is competing in.
References.

Please email the system description to the competition organizers.

System Properties

The ATP systems have to be executable by a single command line, with the file name, the time limit (if required by the entrant), and entrant specified system switches (the same for all problems) as command line arguments. No shell features, such as input or output redirection, may be used in the command line.

The ATP systems that run on the general hardware have to be interruptable by a SIGXCPU signal, so that the CPU time limit can be imposed on each solution attempt. The default action on receiving this signal is to exit (thus complying with the time limit, as required), but systems may catch the signal and exit of their own accord. Both approaches are acceptable for the competition. If any system runs past the time limit this will be noticed in the timing data and the system will be considered to have not solved that problem. In the Special Hardware Division the wall clock time limit will be imposed using SIGALRM.

When terminating, the ATP systems have to output a distinguished string (specified by the entrant) to stdout indicating the result:

A proof exists, or
The problem is satisfiable, or
No solution found.

The ATP systems are not required to output solutions (proofs or models). However, systems that do output solutions to stdout will be highlighted in the presentation of results. For practical reasons excessive output from the ATP systems is not allowed. A limit, dependent on the disk space available, will be imposed on the amount of stdout and stderr output that can be produced. The limit will be at least 10KB per problem (averaged over all problems so that it is possible to produce some long proofs).

The precomputation and storage of any information for individual TPTP problems for usage during the competition is contrary to the spirit of the competition, and the no cheating rule applies. The precomputation and storage of information for sets of formulae that are reasonably likely to form the basis of new problems is permitted. For every problem solved, the system's solution process has to be reproducible by running the system again.

System Installation

Access to the general hardware (or equivalent) will be made available from the 21th June 1999, and the entrants have to have their ATP systems installed and operational by 2nd July 1999. No late systems will be accepted.

Entrants have to ensure that their systems execute in the competition environment, according to the checks listed below. Entrants are advised to firstly perform these checks on their own machines, well in advance of the installation period. This gives the competition organizers time to help resolve any difficulties that are encountered. Secondly, entrants must perform these checks on the general hardware. Systems that do not pass these checks on the general hardware cannot compete.

The ATP system can be run by an absolute path to the executable. For example:

prompt>which MyATPSystem
/home/tptp/bin/MyATPSystem
prompt>/home/tptp/bin/MyATPSystem /home/tptp/TPTP/Problems/GRP/GRP001-1.p
Proof found in 147 seconds.
prompt>

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/GRP001-1.p CCC001-1.p
prompt> /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p
Proof found in 147 seconds.
prompt>

The ATP system's CPU time can be limited using the CPULimitedRun.c program. For example:

prompt>which CPULimitedRun
/home/tptp/bin/CPULimitedRun
prompt>/home/tptp/bin/CPULimitedRun 10 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p
CPULimitedRun: ----------------------------------------------------------
CPULimitedRun: /home/tptp/bin/MyATPSystem
CPULimitedRun: Time limit is 10s
CPULimitedRun: PID is 5827
CPULimitedRun: ----------------------------------------------------------
CPU time limit exceeded (core dumped)
prompt>

The CPU time taken by a CPU limited run can be measured by /bin/time. For example:

prompt> /bin/time /home/tptp/bin/CPULimitedRun 200 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p
CPULimitedRun: ----------------------------------------------------------
CPULimitedRun: /home/tptp/bin/MyATPSystem
CPULimitedRun: Time limit is 200s
CPULimitedRun: PID is 13526
CPULimitedRun: ----------------------------------------------------------
Proof found in 147 seconds.

real     3:04.2
user     2:19.3
sys         7.6
prompt>

The timed command can be run in an rsh. The timed command needs to be quoted, and don't forget to make an appropriate rhosts entry. For example:

prompt> rsh atoll.cs.jcu.edu.au '/bin/time /home/tptp/bin/CPULimitedRun 200 /home/tptp/bin/MyATPSystem /home/tptp/tmp/CCC001-1.p'
CPULimitedRun: ----------------------------------------------------------
CPULimitedRun: /home/tptp/bin/MyATPSystem
CPULimitedRun: Time limit is 200s
CPULimitedRun: PID is 25461
CPULimitedRun: ----------------------------------------------------------
Proof found in 147 seconds.

real     3:04.2
user     2:19.3
sys         7.6

After the installation deadline access to the general hardware will be denied, and no further changes to the ATP systems will be permitted. The organizers will then test the ATP systems, first to check that the systems execute correctly (according to the above checks), and secondly to check for soundness.

For the soundness testing, non-theorems (satisfiable variants of the eligible problems, e.g., without the conjecture clause, and satisfiable problems selected from the TPTP) will be submitted to the systems participating in the MIX, UEQ, and FOF Divisions, and theorems (selected from the TPTP) will be submitted to the systems participating in the SAT Division. Finding a proof of a non-theorem or a model for a theorem indicates that the system is unsound. If an ATP system fails the soundness testing it will be disqualified. The soundness testing has a secondary aim of eliminating the possibility of an ATP system simply delaying for some amount of time and then claiming to have found a solution. Further soundness testing will be performed after the competition, as described in the section on Performance Evaluation.

In the Special Hardware Division the systems will be installed on the respective hardware by the entrants, and no soundness testing needs to be performed.

System Execution

Execution of the ATP systems on the general hardware will be controlled by a perl script, provided by the competition organizers. The jobs will be 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 will be started before any attempts at the (N+1)th problems.

During the competition a perl script will parse the systems' output. If an ATP system's success string is found then the timing information from the time command will be extracted. The CPU time taken, or the time limit if no solution was found, will be recorded. This data will be used to generate an HTML-file, and a WWW-browser will be used to display the results.

The execution of the Special Hardware Division systems will be supervised by their entrants.

Performance Evaluation

The systems will be ranked within each competition division and category according to the number of problems solved. If several systems solve the same number of problems, then those systems will be ranked according to their average runtimes over solutions found. If any division or category is won by the CASC-15 entrant, then no winner will be announced in that division or category. Otherwise winners will be announced in each division and category, and prizes will be awarded.

If only one ATP system registers for a particular competition division, no winner can be announced for that division, but the results for that system will still be presented.

At some time after the competition, all high ranking systems in each division will be tested over the entire TPTP. This testing will provide a final check for soundness, and any system found to be unsound will be retrospectively disqualified.