%------------------------------------------------------------------------------
% File     : MSC015-1.010 : TPTP v8.2.0. Released v3.5.0.
% Domain   : Miscellaneous
% Problem  : Binary counter k=10
% Version  : Especial.
% English  : Each instance of the problem asserts
%              p(0*).                 // p[0]
%              p(x*01*) -> p(x*10*).  // p[i] -> p[i + 1]
%              not p(1*).             // not p[2^n - 1]
%            These problems are unsatisfiable and have exponentially large
%            propositional resolution refutations, while there is a short
%            (quadratic) first order refutation.

% Refs     : [NV07a] Navarro (2007), Email to Geoff Sutcliffe
%            [NV07b] Navarro & Voronkov (2007), Planning with Effectively P
% Source   : [NV07a]
% Names    : bincount-k10 [NV07a]

% Status   : Unsatisfiable
% Rating   : 0.00 v3.5.0
% Syntax   : Number of clauses     :   12 (   2 unt;   0 nHn;  12 RR)
%            Number of literals    :   22 (   0 equ;  11 neg)
%            Maximal clause size   :    2 (   1 avg)
%            Maximal term depth    :    1 (   1 avg)
%            Number of predicates  :    1 (   1 usr;   0 prp; 10-10 aty)
%            Number of functors    :    2 (   2 usr;   2 con; 0-0 aty)
%            Number of variables   :   45 (   0 sgn)
% SPC      : CNF_UNS_EPR_NEQ_HRN

% Comments : k >= 23 not solved by any prover in less than 1 hr. (2007)
%------------------------------------------------------------------------------
cnf(init,axiom,
    p(s0,s0,s0,s0,s0,s0,s0,s0,s0,s0) ).

cnf(rule1,axiom,
    ( ~ p(X0,X1,X2,X3,X4,X5,X6,X7,X8,s0)
    | p(X0,X1,X2,X3,X4,X5,X6,X7,X8,s1) ) ).

cnf(rule2,axiom,
    ( ~ p(X0,X1,X2,X3,X4,X5,X6,X7,s0,s1)
    | p(X0,X1,X2,X3,X4,X5,X6,X7,s1,s0) ) ).

cnf(rule3,axiom,
    ( ~ p(X0,X1,X2,X3,X4,X5,X6,s0,s1,s1)
    | p(X0,X1,X2,X3,X4,X5,X6,s1,s0,s0) ) ).

cnf(rule4,axiom,
    ( ~ p(X0,X1,X2,X3,X4,X5,s0,s1,s1,s1)
    | p(X0,X1,X2,X3,X4,X5,s1,s0,s0,s0) ) ).

cnf(rule5,axiom,
    ( ~ p(X0,X1,X2,X3,X4,s0,s1,s1,s1,s1)
    | p(X0,X1,X2,X3,X4,s1,s0,s0,s0,s0) ) ).

cnf(rule6,axiom,
    ( ~ p(X0,X1,X2,X3,s0,s1,s1,s1,s1,s1)
    | p(X0,X1,X2,X3,s1,s0,s0,s0,s0,s0) ) ).

cnf(rule7,axiom,
    ( ~ p(X0,X1,X2,s0,s1,s1,s1,s1,s1,s1)
    | p(X0,X1,X2,s1,s0,s0,s0,s0,s0,s0) ) ).

cnf(rule8,axiom,
    ( ~ p(X0,X1,s0,s1,s1,s1,s1,s1,s1,s1)
    | p(X0,X1,s1,s0,s0,s0,s0,s0,s0,s0) ) ).

cnf(rule9,axiom,
    ( ~ p(X0,s0,s1,s1,s1,s1,s1,s1,s1,s1)
    | p(X0,s1,s0,s0,s0,s0,s0,s0,s0,s0) ) ).

cnf(rule10,axiom,
    ( ~ p(s0,s1,s1,s1,s1,s1,s1,s1,s1,s1)
    | p(s1,s0,s0,s0,s0,s0,s0,s0,s0,s0) ) ).

cnf(goal,negated_conjecture,
    ~ p(s1,s1,s1,s1,s1,s1,s1,s1,s1,s1) ).

%------------------------------------------------------------------------------