The CADE ATP System Competition
Design and Organization
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.
It is assumed that all entrants have read the web pages related
to the competition, and have complied with the competition rules.
Non-compliance with the rules could lead to disqualification.
A "catch-all" rule is used to deal with any unforeseen 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.
Every effort has been made to organize the competition in a fair and
No responsibility is taken if, for one reason or the other, your system
does not win.
The design and procedures of this CASC evolved from those of
Important changes for this CASC are:
- The competition will be run on
Systems must be delivered as StarExec installation packages.
- Systems must use the
SZS ontology and standards
for reporting their results.
- The LTB division is having a one year hiatus.
- The UEQ division returned from its three year hiatus.
CASC is divided into divisions according to problem and system characteristics.
There are competition divisions in which systems are explicitly
ranked, and a demonstration division in which systems demonstrate
their abilities without being ranked.
Some divisions are further divided into problem categories, which
makes it possible to analyse, at a more fine grained level, which systems
work well for what types of problems.
The problem categories have no effect on the competition rankings, which
are made at only the division level.
The competition divisions are open to ATP systems that meet the required
Each division uses problems that have certain logical, language, and syntactic
characteristics, so that the ATP systems that compete in the division are, in
principle, able to attempt all the problems in the division.
In the following effectively propositional means that the problem
is known to be reducible to a propositional problem, e.g., a CNF problem
that has no functions with arity greater than zero.
The problems section explains what problems are
eligible for use in each division and category.
The system evaluation section explains how the
systems are ranked in each division.
- The THF division:
Typed Higher-order Form theorems (axioms with a provable conjecture),
using the TH0 syntax.
The THF division has two problem categories:
- The TNE category: THF with No Equality
- The TEQ category: THF with EQuality
- The TFA division:
Typed First-order with Arithmetic theorems (axioms with a provable
conjecture), using the TF0 syntax.
The TFA division has three problem categories:
- The TFI category: TFA with only Integer arithmetic
- The TFR category: TFA with only Rational arithmetic
- The TFE category: TFA with only Real arithmetic
- The FOF division:
First-Order Form syntactically non-propositional theorems (axioms with
a provable conjecture).
The FOF division has two problem categories:
- The FNE category: FOF with No Equality
- The FEQ category: FOF with EQuality
- The FNT division:
First-order form syntactically non-propositional Non-Theorems (axioms
with a countersatisfiable conjecture, and satisfiable axiom sets).
The FNT division has two problem categories:
- The FNN category: FNT with No equality
- The FNQ category: FNT with eQuality
- The EPR division:
Effectively PRopositional (but syntactically non-propositional) clause
normal form theorems and non-theorems (clause sets).
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 UEQ division:
Unit EQuality not effectively propositional clause normal form theorems
(unsatisfiable clause sets).
ATP systems that cannot run in the competition divisions for any reason
(e.g., the system requires special hardware, or the entrant is an organizer)
can be entered into the demonstration division.
Demonstration division systems can run on the competition computers, or on
computers supplied by the entrant.
The entry specifies which competition divisions' problems are to be used.
The demonstration division results are presented along with the competition
divisions' results, but might not be comparable with those results.
The systems are not ranked and no prizes are awarded.
The computers have:
Each ATP system runs one job on one computer at a time.
Systems may use all the cores on the computers (although this does not
necessarily help, because a CPU time limit is imposed).
- Four (a quad-core chip) Intel(R) Xeon(R) E5-2609, 2.40GHz CPUs
- 256GB memory
- The Red Hat Enterprise Linux Workstation release 6.3 (Santiago)
operating system, kernel 2.6.32-431.1.2.el6.x86_64
Problems for CASC are taken from the
TPTP Problem Library.
The TPTP version used for CASC is released after the competition has started,
so that new problems have not been seen by the entrants.
The problems have to meet certain criteria to be eligible for selection:
The problems used are randomly selected from the eligible problems at the
start of the competition, based on a seed supplied by the competition panel.
- The TPTP uses system performance data to compute problem difficulty
Problems with a rating in the range 0.21 to 0.99 are eligible.
Problems of lesser and greater ratings might also be eligible
in some divisions if there are not enough problems with the desired
Performance data from systems submitted by the
system submission deadline is used for computing the problem
ratings for the TPTP version used for the competition.
- 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)
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 must 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
(the competition organizers have to ensure that there are sufficient computers
available to run the ATP systems on this minimal number of problems).
The minimal numbers of problems are used in determining the
time limits imposed on each solution attempt.
A lower bound on the total number of problems to be used is determined from
the number of computers available,
the time allocated to the competition,
the number of ATP systems to be run on the competition computers over all the
the time limit per problem,
according to the following relationship:
NumberOfComputers * TimeAllocated
NumberOfProblems = ---------------------------------
NumberOfATPSystems * TimeLimit
It is a lower bound on the total number of problems because it assumes that
every system uses all of the time limit for each problem.
Since some solution attempts succeed before the time limit is reached, more
problems can be used.
The numbers of problems used in each division and problem category are
(roughly) proportional to the numbers of eligible problems, 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.
The problems are in TPTP format, with include directives.
The problems in each division are given in increasing order of
TPTP difficulty rating.
In order to ensure that no system receives an advantage or disadvantage
due to the specific presentation of the problems in the TPTP, the problems
are preprocessed to:
- strip out all comment lines, including the problem header
- randomly reorder the formulae/clauses
(include directives are left before formulae,
type declarations and definitions are kept before the symbols' uses)
- randomly swap the arguments of associative connectives, and
randomly reverse implications
- randomly reverse equalities
In the demonstration division the same problems are used as for the
competition divisions, with the same preprocessing applied.
However, the original file names can be retained for systems running
on computers provided by the entrant.
CPU and wall clock time limits are imposed.
The minimal CPU time limit per problem is 240s.
The maximal CPU time limit per problem is determined using the relationship
used for determining the number of problems, with the minimal number of
problems as the NumberOfProblems.
The CPU time limit is chosen as a reasonable value within the range allowed,
and is announced at the competition.
The wall clock time limit is imposed in addition to the CPU time limit, to
limit very high memory usage that causes swapping.
The wall clock time limit per problem is double the CPU time limit.
An additional memory limit is imposed, depending on the
The time limits are imposed individually on each solution attempt.
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
For each ATP system, for each problem, four items of data are recorded:
whether or not the problem was solved,
the CPU time taken,
the wall clock time taken,
and whether or not a solution (proof or model) was output.
The systems are ranked in the competition divisions, from the performance data.
The THF, TFA, EPR, and UEQ
divisions have an assurance ranking class, ranked according to the
number of problems solved, but not necessarily accompanied by a proof or
model (thus giving only an assurance of the existence of a proof/model).
The FOF and FNT divisions have a proof/model ranking
class, ranked according to the number of problems solved with an acceptable
Ties are broken according to the average time over problems solved.
In the competition divisions winners are announced and prizes are
The competition panel decides whether or not the systems' proofs and models are
acceptable for the proof/model ranking classes.
The criteria include:
In the assurance ranking classes the ATP systems are not required to
output solutions (proofs or models).
However, systems that do output solutions are highlighted in the presentation
- Derivations must be complete, starting at formulae from the problem,
and ending at the conjecture (for axiomatic proofs) or a false
formula (for proofs by contradiction, including CNF refutations).
- For proofs of FOF problems by CNF refutation, the conversion from
FOF to CNF must be adequately documented.
- Derivations must show only relevant inference steps.
- Inference steps must document the parent formulae, the inference rule
used, and the inferred formula.
- Inference steps must be reasonably fine-grained.
- An unsatisfiable set of ground instances of clauses is acceptable for
establishing the unsatisfiability of a set of clauses.
- Models must be complete, documenting the domain, function maps,
and predicate maps.
The domain, function maps, and predicate maps may be specified by
explicit ground lists (of mappings), or by any clear, terminating
In addition to the ranking criteria, other measures are made and presented
in the results:
- The state-of-the-art contribution (SOTAC) quantifies the unique
abilities of each system.
For each problem solved by a system, its SOTAC for the problem is the
inverse of the number of systems that solved the problem.
A system's overall SOTAC is its average SOTAC over the problems it solves.
- The efficiency measure balances the number of problems solved
with the time taken.
It is the average of the inverses of the times for problems solved
(with times less than the timing granularity
rounded up to the granularity, to avoid skewing caused by very low times)
multiplied by the fraction of problems solved.
This can be interpreted intuitively as the average of the solution rates
for problems solved, multiplied by the fraction of problems solved.
- The core usage is the average of the ratios of CPU time to
wall clock time used, over the problems solved.
This measures the extent to which the systems take advantage the
At some time after the competition, all high ranking systems in the
competition divisions are tested over the entire TPTP.
This provides a final check for soundness (see the section on
system properties regarding soundness
checking before the competition).
If a system is found to be unsound during or after the competition, but
before the competition report is published, 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 and models from the winners
of the proof/model ranking classes 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
All disqualifications are explained in the competition report.
To be entered into CASC, systems must be registered using the
CASC system registration form.
No registrations are accepted after the
For each system entered, an entrant must be nominated to handle all issues
(including execution difficulties) arising before and during the competition.
The nominated entrant must
formally register for CASC.
It is not necessary for entrants to physically attend the competition.
Systems can be entered at only the division level, and can be entered
into more than one division
(a system that is not entered into a competition division is assumed to
perform worse than the entered systems, for that type of problem -
wimping out is not an option).
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.
Systems that rely essentially on running other ATP systems without adding
value are deprecated; the competition panel may disallow or move such
systems to the demonstration division.
The division winners of the previous CASC
are automatically entered into their divisions, to provide benchmarks
against which progress can be judged.
A system description must be provided for each ATP system entered, using
this HTML schema.
The schema has the following sections:
- Architecture. This section introduces the ATP system, and describes
the calculus and inference rules 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
- 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.
The availability of the system is also given here.
- Expected competition performance. This section makes some
predictions about the performance of the ATP system in each of the
divisions and categories in which it is competing.
The system description must be emailed to the competition organizers by
the system description deadline.
The system descriptions, along with information regarding the competition
design and procedures, form the proceedings for the competition.
For systems in the proof/model classes, representative sample solutions must
be emailed to the competition organizers by the
sample solutions deadline.
Use of the TPTP format for
interpretations is encouraged.
The competition panel decides whether or not proofs and models are
acceptable for the proof/model ranking classes.
Proof samples for proof classes must include a proof for
Model samples for model classes must include models for
The sample solutions must illustrate the use of all inference rules.
An explanation must be provided for any non-obvious features.
Entrants must ensure that their systems execute in a competition-like
environment, and have the following properties.
Entrants are advised to finalize their installation packages and check these
well in advance of the system delivery deadline.
This gives the competition organizers time to help resolve any difficulties
Soundness and Completeness
- Systems must be sound.
At some time before the competition all the systems in the competition
divisions are tested for soundness.
Non-theorems are submitted to the systems in the
THF, TFA, FOF, EPR, and UEQ
divisions, and theorems are submitted
to the systems in the FNT and EPR divisions.
Finding a proof of a non-theorem or a disproof of a theorem indicates
If a system fails the soundness testing it must be repaired by
the unsoundness repair deadline or be
For systems running on computers supplied by the entrant in the
demonstration division, the entrant must perform the soundness testing
and report the results to the competition organizers.
- Systems do not have to be complete in any sense, including
calculus, search control, implementation, or resource requirements.
- All techniques used must be general purpose, and expected to extend
usefully to new unseen problems.
The precomputation and storage of information about individual TPTP
problems or their solutions is not allowed.
Strategies and strategy selection based on individual problems
or their solutions are not allowed.
If machine learning procedures are used, the learning must ensure that
sufficient generalization is obtained so that no there is no
specialization to individual problems or their solutions.
- The system's performance must be reproducible by running the system again.
- Systems must run on StarExec.
(the competition computers).
ATP systems that cannot run on the competition computers can be entered
into the demonstration division.
- Systems must be fully automatic, i.e., all command line switches have
to be the same for all problems in each division.
- For each problem, the system must output a distinguished string
indicating what solution has been found or that no conclusion has been
Systems must use the
SZS ontology and standards for this.
% SZS status Theorem for SYN075+1
% SZS status GaveUp for SYN075+1
- When outputting proofs/models, the start and end of the proof/model must
be delimited by distinguished strings.
Systems must use the
SZS ontology and standards for this.
% SZS output start CNFRefutation for SYN075+1
% SZS output end CNFRefutation for SYN075+1
The string specifying the problem status must be output before the start
of a proof/model.
Use of the TPTP format for
interpretations is encouraged.
- Systems that run on the competition computers must be
interruptible by a SIGXCPU signal, so that the CPU time limit
can be imposed, and interruptable by a SIGALRM signal,
so that the wall clock time limit can be imposed.
For systems that create multiple processes, the signal is sent first to
the process at the top of the hierarchy, then one second later to all
processes in the hierarchy.
The default action on receiving these signals is to exit (thus complying
with the time limit, as required), but systems may catch the signals
and exit of their own accord.
If a system runs past a time limit this is noticed in the timing
data, and the system is considered to have not solved that problem.
- If an ATP system terminates of its own accord, it may not leave any
temporary or intermediate output files.
If an ATP system is terminated by a SIGXCPU or SIGALRM,
it may not leave any temporary or intermediate output files anywhere other
than in /tmp.
- For practical reasons excessive output from an ATP system is not
A limit, dependent on the disk space available, is imposed on the amount
of output that can be produced.
For systems running on the competition computers, entrants must email a
StarExec installation package to the competition organizers by the
system delivery deadline.
The installation package must be a .tgz file containing
only the components necessary for running the system (i.e., not including
source code, etc.).
The entrants must also email a .tgz file containing the source
code and any files required for building the StarExec installation package
to the competition organizers by the system delivery
For systems running on entrant supplied computers in the demonstration
division, entrants must deliver a source code package to the competition
organizers by the start of the competition.
The source code package must be a .tgz file containing
the system source code.
After the competition all competition division systems' source code
is made publicly available on the CASC web site.
In the demonstration division, the entrant specifies whether or not
the source code is placed on the CASC web site.
An open source license is
Execution of the ATP systems on the competition computers is controlled by
The jobs are queued onto the computers so that each computer 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
A system has solved a problem iff it outputs its termination string within
the time limit, and a system has produced a proof/model iff it outputs
its end-of-proof/model string within the time limit.
The result and timing data is used to generate an HTML file, and a web
browser is used to display the results.
The execution of the demonstration division systems is supervised by
- Check: You can
login to StarExec. If not,
apply for an account in the TPTP community.
- Check: You can access the TPTP v6.0.0 space. If not,
email the competition organizers.
- Check: You can create and upload a
StarExec installation package.
The competition organizers have examplar StarExec installation packages
that you can use as a starting point - email the competition organizers
to get one that is appropriate for your ATP system.
- Check: You can create a job and run it, and your ATP system gets the
Use the SZS post processor.
- Check: Your ATP system can solve a problem that has include
Because of the way StarExec runs jobs, your ATP system must implement
the TPTP requirement ... "Include files with relative path names are
expected to be found either under the directory of the current file,
or if not found there then under the directory specified in the
TPTP environment variable."
- Check: You can email your StarExec installation package to the
competition organizer for testing.